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

---

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