Broken Address Bus

문제

The memory in Juku's computer has $NN$ cells, addressed by numbers $0\dots N-10\; \backslash ldots\; N-1$. To read the value from a cell, you first have to put the cell's address on the address bus. The address bus consists of $1616$ parallel wires---one for each bit of the address. E.g., to read the value at the address $1919$, you first write $1919$ out in binary---$19=2^4+2^1+2^0=(10011{)}_{2}19\; =\; 2^4\; +\; 2^1\; +\; 2^0\; =\; (10011)\_2$---and then put voltage on wires $44$, $11$, and $00$. To read from the address $00$, you don't put voltage on any of the wires.

However, some wires are broken---when you put voltage on any of them, the memory chip will not register it. E.g, if the wire $00$ is broken, you cannot read from the address $7=2^2+2^1+2^{0}7\; =\; 2^2\; +\; 2^1\; +\; 2^0$ because it requires voltage on the wire $00$. On the other hand, you still can read from $6=2^2+2^{1}6\; =\; 2^2\; +\; 2^1$.

Given the contents of the memory and the set of all intact wires, compute the sum of all the values you can read.

입력

The first line of input contains $NN$ ($1\le N\le 2^{16}1\; \backslash le\; N\; \backslash le\; 2^\{16\}$), the number of values in memory, and $QQ$ ($1\le Q\le {10}^{5}1\; \backslash le\; Q\; \backslash le\; 10^5$), the number of queries. The next $NN$ lines contain the values in memory cells, from $00$ to $N-1N-1$, one per line. Each value is a non-negative integer not larger than ${10}^{9}10^9$. The last $QQ$ lines contain the queries. Each query gives the address $X_{i}X\_i$ () that you get when you put voltage on all the wires that are not broken.

출력

The output must contain $QQ$ lines, each with the answer to the corresponding query: the sum of the values that can be read from the memory if the set of working address bus wires is as given in the query parameter $X_{i}X\_i$.

힌트

In the query '0', all wires are broken, and only the value $1010$ at address $00$ is readable.

In the query '15', the first $44$ wires are working and all values are readable.

In the last query, only the values $1010$ and $11$ are readable.

3 3
10
7
1
0
15
2

10
18
11