### PROBLEM LINK:

**Author:** Erfan alimohammadi

**Tester & Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Easy

### PREREQUISITES:

None

### PROBLEM:

An N-bonacci sequence is an infinite sequence F_1,F_2,… such that for each integer i>N:

F_i =F_{i−1}⊕F_{i−2}⊕…⊕F_{i−N} where ⊕ denotes the bitwise XOR operation.

Recently, Chef has found an interesting sequence S_1,S_2,… , which is obtained from prefix XORs of a XOR N-bonacci sequence F_1,F_2,….

Formally, for each positive integer i :

S_i=F_1⊕F_2⊕…⊕F_i.

You are given the first N elements of the sequence F, which uniquely determine the entire sequence S.

You should answer Q queries. In each query, you are given an index k and you should calculate S_k. It is guaranteed that in each query.

1\leq N,Q \leq 10^5

1\leq K \leq 10^9

### EXPLANATION:

Let’s mention some important observations:

F_{N+1} \,=\, F_1⊕F_2⊕…⊕F_N

Let’s take one step forward and calculate F_{N+2}. You will notice that:

F_{N+2} \, = \, F_2⊕F_3⊕F_4⊕…⊕F_N⊕F_{N+1}

We already defined F_{N+1} and we know that X⊕X=0

So we conclude F_{N+2} = F_1

Based on the same terminology, we can see that our sequence F look like this:

\{F_1,F_2,F_3,...,F_N, \,TotalXor \, ,F_1,F_2,F_3,...,F_N,\, TotalXor \,,....\}

Now as defined in the problem statement:

S_i = F_1⊕F_2⊕…⊕F_N

Let’s calculate the value of S_i for each i such that (1 \leq i \leq N+1) We can do that in linear time.

You should notice that S_{N+1}=0 because all elements are included twice in its total expression.

So At last:

S_K = S_{K\,mod\,N+1}

Assuming that S_0=0 since it represents empty sequence.

Complexity: O(N)