'Arijit Singh ke gaano ke baad bachpan se single log bhi apni EX ko yaad karne lag jaate hain!'

This is the problem with ACM. The \(Single / Commited\) ratio is too high. To tackle the problem, ACM is planning to launch a Scheme in which every person to solve the given problem will get a chance to go on a date with anyone he/she likes.

You are given an array A of size N. Let's define EX-Factor of a subsequence\(A_1, A_2, A_3, A_4...A_K\) as:

\(EX-Factor = A_1 - A_2 + A_3 - A_4 ... (-1^{K-1}) * A_K\)

You have to answer multiple queries.

Each query contains an integer X. Find the number of subsequences with EX-Factor equal to X.

NOTE: The first person to solve this problem is free to negotiate for reimbursement of the date.

INPUT FORMAT:

First-line contains an integer, N.

Next line contains N space-separated integers, \(A_i\).

The next line contains Q, the number of queries.

Each of the following Q lines contains X mentioned above.

OUTPUT FORMAT:

Output answers for each query in a new line.

CONSTRAINTS:

\(1 <= N <= 32\)

\(1 <= Q <= 100\)

\(-10^9 <= A_i <= 10^9\)

\(-10^9 <= X <= 10^9\)