Noodle Cutting Puzzle

You are given n noodles with lengths L₁, L₂, …, L_n. You are allowed to perform the following operation any number of times (possibly zero) on any noodle:

• If a noodle has an even length, you may cut it into two noodles of equal length (i.e. replace a noodle of length L with two noodles of length L/2).

After performing any sequence of such operations (operations on different noodles are independent), you end up with a multiset of noodles. For each noodle, you are allowed to either leave it uncut or cut it several times. However, note that you can only cut an even-length noodle. Thus, for a noodle with L = 2^a×m</sup> (where m is odd), you can perform at most a cuts on it. In fact, if you choose to cut it exactly t times (with 0 ≤ t ≤ a), then the noodle will yield 2^t pieces, each of length L/(2^t) = 2^a-t×m.

The product of the lengths of the noodles in the final configuration is then

[ P = \prod_{i=1}^{n} \Bigl(\frac{L_i}{2^{t_i}}\Bigr)^{2^{t_i}}, ]

where for each noodle i you choose an integer t_i with 0 ≤ t_i ≤ v₂(L_i). Write each L_i as 2^a_i×m_i (with m_i odd). Then, when you choose t_i cuts on the i-th noodle, its contribution becomes

[ \Bigl(2^{a_i-t_i},m_i\Bigr)^{2^{t_i}} = 2^{(a_i-t_i)\cdot 2^{t_i}},, m_i^{2^{t_i}}. ]

You are given m independent queries. Each query consists of 6 non‐negative integers

[ a; b; c; d; e; f, ]

and asks whether it is possible to choose a nonnegative integer t_i (0 ≤ t_i ≤ a_i) for each noodle such that the final product equals

[ R = 2^a \times 3^b \times 5^c \times 7^d \times 11^e \times 13^f. ]

If it is possible, output 1; otherwise, output 0. Note that the splitting operations on the noodles are independent between queries.

inputFormat

The first line contains a single integer n, the number of noodles.

The second line contains n space‐separated positive integers representing the lengths L₁, L₂, …, L_n.

The third line contains a single integer m, denoting the number of queries.

Then follow m lines, each containing 6 non‐negative integers: a b c d e f.

outputFormat

For each query, output a single line containing 1 if it is possible to achieve the target product, or 0 otherwise.

sample

1
6
3
1 1 0 0 0 0
0 2 0 0 0 0
1 2 0 0 0 0

1
1
0