说明

给你 $n$ 根面条，长度为 $\{l_1,l_2,l_3,\cdots,l_n\}$，你可以进行若干次以下操作：

• 选取一根长度为偶数的面条，把它平均切成两根面条。

有 $m$ 次询问（每次询问独立）：

• a b c d e f：请判断能否切完面条后让面条长度的乘积等于 $R=2^a\times3^b\times5^c\times7^d\times11^e\times13^f$；若能则输出 1，否则输出 0。

输入格式

共 $2+m$ 行。

第一行 $2$ 个正整数，分别为 $n$ 和 $m$，含义见题面。

第二行 $n$ 个正整数，分别为 $l_1,l_2,l_3,\cdots,l_n$，含义见题面。

第 $3\sim 2+m$ 行每行 $6$ 个非负整数，分别为 $a,b,c,d,e,f$，含义见题面。

输出格式

共 $m$ 行。

第 $1\sim m$ 行，每行输出 1 或 0，含义见题面。

6 4
2 4 6 12 9 11
6 4 0 0 1 0 
5 5 0 0 1 0
0 8 0 0 1 0
0 8 0 0 2 0

1
1
1
0

提示

数据：

$R=2^a\times3^b\times5^c\times7^d\times11^e\times13^f$ | Subtask | $n$ | $l_i$ | $a,b,c,d,e,f$ | $R$ | pts | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $\le10$ | $1\le l_i\le13$ | $\le80$ | $\le10^6$ | $10$ | | $1$ | $\le10$ | $1\le l_i\le13$ | $\le10$ | 无特殊限制 | $10$ | | $2$ | $\le80$ | $1\le l_i\le13$ | $\le80$ | 无特殊限制 | $20$ | | $3$ | $\le10^5$ | $1\le l_i\le13$ | $\le4\times10^5$ | 无特殊限制 | $60$ |

对于所有数据，$1\le n\le 10^5$，$1\le l_i\le 13$，$1\le m\le10^5$，$0\le a,b,c,d,e,f\le4\times10^5$。