D. Weights II

Merchants measured many commodities using weights and a two-pan balance. If you are using a limited set of weights, however, you can only measure certain quantities accurately. For example, suppose that you have only two weights: a 1-ounce weight and a 3-ounce weight. With these you can easily measure out 4 ounces, as shown in Figure1.

It is somewhat more interesting to discover that you can also measure out 2 ounces by shifting the 1-ounce weight to the other side, as shown in Figure2.

Write a program to determine whether it is possible to measure out the desired target amount with a given set of weights.

输入格式

First line contains a single integer \( t(t<1000 ) \)

The first line of each test case contains an integers \( n( 1\leq n \leq 100)\) – thesize of the given set of weights.

The second line of each test case contains \( n \)integers\( w_1,w_2,\cdots, w_n( 1\leq w_i \leq 10^4 )\)

The third line of each test case contains an integer\( q(1\leq q \leq 10^4 )\)– thenumber of queries.

The fourth line of each test cases contains distinct integers – the desired target amounts.

It’s guaranteed that the sum of all does not exceed \( 10^4\).

输出格式

For each test case, output a binary string ,\( s\) s.t. \(s_i=1 \) if it is possible measure out the desired target amount \( W_i\) with the given set of weights and \( s_i=0 \) otherwise.

测试样例

Input

3
2
1 3
6
1 2 3 4 5 6
2
1 4
6
1 2 3 4 5 6
3
3 5 9
18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Output

111100
101110
111111111011010010