Tara recently discovered that each integer can be factored into prime numbers. She first found the process of factoring numbers really exciting, but quickly grew tired of its repetitiveness.

In order to make factoring more challenging, she has decided to limit the factors that she’s allowed to use to ~N~ of her favourite numbers. She would now like to figure out which numbers are factorable using the ~N~ numbers. Can you help her out?

Input Specification

The input begins with an integer ~N~ ~(1 \le N \le 10^5)~, the number of factors that Tara is allowed to use.

The second line contains ~N~ integers ~A_i~ ~(1 \le A_i \le 10^6)~, the allowed factors.

The third line contains a single integer ~M~ ~(1 \le M \le 10)~, the number of integers to factor.

The fourth line contains ~M~ integers ~B_i~ ~(2 \le B_i \le 10^{12})~, the numbers to factor.

For at least 20% of points, each ~A_i~ will be prime.

For at least 50% of points, ~N \le 40~.

Output Specification

For each of the ~M~ numbers to factor, output a 1 if it is possible to factor the number using the allowed factors, or 0 otherwise. Each number should be considered independently of the rest.

Sample Input 1

4
2 5 6 8
4
10 4 48 15

Sample Output 1

1110