+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- 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 ```