• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

A sequence is called $N$-Bonnaci if it is calculated from its previous $N$ elements. An XOR $N$-Bonacci sequence can be formulated in the following format:

$$F(K) = F(K - 1) \oplus F(K - 2) \oplus \dots \oplus F(K - N + 1) \oplus F(K - N)$$

Here $\oplus$ denotes bitwise XOR operation. Newbies jury have recently found an interesting sequence which is obtained from the XOR operation on the first $K$ elements of the XOR $N$-Bonacci sequence:

$$S(K) = F(1) \oplus F(2) \oplus \dots \oplus F(K - 1) \oplus F(K)$$

It can be proven that for calculating all of the $N$-Bonacci Numbers, only the first $N$ elements are need to be known. Given the first $N$ numbers of the XOR $N$-Bonacci sequence, your task is to calculate $S(K)$ for $Q$ queries.

ورودی

The first line of the input contains two space separated integers $N$ $Q$. The second line contains $N$ space separated integers denoting $F(1), F(2), \dots , F(N)$ respectively. Each of the next $Q$ lines, describes a query by giving an integer $K$.

$$1 \leq N, Q \leq 10^5$$

خروجی

For each query, you should print the $S(K)$ in a line.

مثال‌ها

ورودی نمونه ۱

3 4
0 1 2
7
2
5
1000000000

خروجی نمونه ۱

3
1
0
0