XOR Nbonacci Sequence

All submissions for this problem are available.
###Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK104/hindi/NBONACCI.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK104/mandarin/NBONACCI.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK104/vietnamese/NBONACCI.pdf) and [Bengali](http://www.codechef.com/download/translated/COOK104/bengali/NBONACCI.pdf) as well. An *$N$bonacci sequence* is an infinite sequence $F_1, F_2, \ldots$ such that for each integer $i \gt N$, $F_i$ is calculated as $f(F_{i1}, F_{i2}, \ldots, F_{iN})$, where $f$ is some function. A *XOR $N$bonacci sequence* is an $N$bonacci sequence for which $f(F_{i1}, F_{i2}, \ldots, F_{iN}) = F_{i1} \oplus F_{i−2} \oplus \ldots \oplus F_{i−N}$, where $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Recently, Chef has found an interesting sequence $S_1, S_2, \ldots$, which is obtained from prefix XORs of a XOR $N$bonacci sequence $F_1, F_2, \ldots$. Formally, for each positive integer $i$, $S_i = F_1 \oplus F_2 \oplus \ldots \oplus 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, $S_k$ does not exceed $10^{50}$. ### Input  The first line of the input contains two spaceseparated integers $N$ and $Q$.  The second line contains $N$ spaceseparated integers $F_1, F_2, \ldots, F_N$.  The following $Q$ lines describe queries. Each of these lines contains a single integer $k$. ### Output For each query, print a single line containing one integer $S_k$. ### Constraints  $1 \le N, Q \le 10^5$  $0 \le F_i \le 10^9$ for each $i$ such that $1 \le i \le N$  $1 \le k \le 10^9$ ### Example Input ``` 3 4 0 1 2 7 2 5 1000000000 ``` ### Example Output ``` 3 1 0 0 ```Author:  erfaniaa 
Editorial  https://discuss.codechef.com/problems/NBONACCI 
Tags  cook104, easye, erfaniaa 
Date Added:  16032019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions