K. Cellular Automata
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an infinite 1-dimensional binary array of cells, which is indexed from $$$-\infty$$$ to $$$+\infty$$$. Initially, at time $$$t=0$$$, exactly $$$K$$$ distinct indices $$$P_1, P_2, \dots, P_K$$$ have the value $$$1$$$, and all other indices have the value $$$0$$$.

The array evolves over time steps $$$t=0, 1, 2, \dots$$$. The state of the array at time $$$t+1$$$ is derived from the state at time $$$t$$$ using the following rule for every index $$$i$$$:

$$$$$$ C_i^{(t+1)} = C_{i-1}^{(t)} \oplus C_{i+1}^{(t)} $$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation. (You might recognise this as elementary cellular automata on rule 90)

You must answer $$$Q$$$ queries. Each query consists of a target index $$$X$$$ and a time $$$T$$$. Determine the value of the cell at index $$$X$$$ at time $$$T$$$.

Input

The first line contains two positive integers $$$K$$$ and $$$Q$$$ ($$$1 \le K, Q \le 1000$$$) — the number of initially active cells, and the number of queries respectively.

The second line contains $$$K$$$ distinct integers $$$P_1, P_2, \dots, P_K$$$ ($$$-10^{18} \le P_i \le 10^{18}$$$) — the indices of the cells that are initially $$$1$$$.

The next $$$Q$$$ lines each contains two integers $$$X$$$ and $$$T$$$ ($$$-10^{18} \le X \le 10^{18}$$$, $$$0 \le T \le 1000$$$) — the target index and the time step for the query.

Output

For each query, output a single line containing '1' if the cell at index $$$X$$$ is active at time $$$T$$$, or '0' otherwise.

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

The example test case is illustrated below:


index:    -3 -2 -1  0  1  2  3 
at t=0: ...0  0  0  1  0  0  0...  
at t=1: ...0  0  1  0  1  0  0...  
at t=2: ...0  1  0  0  0  1  0...