L. Ginger's function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$\texttt{Ginger}$$$ has a function

$$$$$$ G(x) = \prod_{i=1}^{n}(1-x^{\lfloor \frac{f_i}{2} \rfloor}-x^{f_i}) $$$$$$

$$$\texttt{Ginger}$$$ decides to give you $$$q$$$ inquiries, given a integer $$$a$$$ for each query, answer the coefficient of $$$x ^ a$$$.

Input

The first line contains two integers $$$n$$$ $$$(1 \le n \le 11)$$$, $$$q$$$ $$$(1 \le q \le 10 ^ 4)$$$.

The second line contains $$$n$$$ integers $$$f_1, f_2, \dots, f_n$$$ $$$(0 \leq f_i \leq 10^6)$$$.

The next $$$q$$$ lines contains a integer $$$a$$$ $$$(0 \leq a \leq \sum_{i = 1} ^ {n} f_i)$$$

Output

output $$$q$$$ lines, Each line print the answer.

Example
Input
2 5
3 4
0
1
2
3
5
Output
1
-1
-1
0
2
Note

For test case:

$$$(1-x-x^3)(1-x^2-x^4) = 1 - x - x^2 - x^4 + 2x^5 + x^7$$$