Vietnamese and Bengali as well.
An $N$-bonacci sequence is an infinite sequence $F_1, F_2, \ldots$ such that for each integer $i > N$, $F_i$ is calculated as $f(F_{i-1}, F_{i-2}, \ldots, F_{i-N})$, where $f$ is some function. A XOR $N$-bonacci sequence is an $N$-bonacci sequence for which $f(F_{i-1}, F_{i-2}, \ldots, F_{i-N}) = F_{i-1} \oplus F_{i−2} \oplus \ldots \oplus F_{i−N}$, where $\oplus$ denotes the bitwise XOR operation.
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 space-separated integers $N$ and $Q$.
- The second line contains $N$ space-separated 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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
n,q=map(int,input().split())
ls=[int(i) for i in input().split()]
cur=0
s=[0]
for i in ls:
 cur=cur^i
 s.append(cur)
for i in range(q):
 k=int(input())
 print(s[k%(n+1)])

# cook your dish here
n,k=list(map(int,input().split()))
d=[0]+list(map(int,input().split()))
l=[0]
for i in range(1,n+1):
 l.append(l[i-1]^d[i])
for q in range(k):
 x=int(input())
 print(l[x%(n+1)])


#!/usr/bin/env python3

(n, q) = input().split()
n = int(n)
q = int(q)
f = [int(fi) for fi in input().split()]
cur = 0
s = [0]
for fi in f:
 cur = cur ^ fi
 s.append(cur)
for i in range(q):
 k = int(input())
 print(s[k % (n + 1)])


# cook your dish here
n,q=list(map(int,input().split(' ')))
ar,xor=list(map(int,input().split(' '))),0

for x in ar: xor^=x
ar.append(xor)

prefix=[0]*(n+1)
prefix[0]=ar[0]

for i in range(1,len(prefix)): prefix[i]=ar[i]^prefix[i-1]
for i in range(q):  print(prefix[(int(input())-1)%(n+1)])


n,q=list([int(x) for x in input().split()])
a=list([int(x) for x in input().split()])
xor_a=0
for i in a:
 xor_a=xor_a^i

a.append(xor_a)
prefix=[a[0]]
for i in range(1,len(a)):
 prefix.append(a[i]^prefix[i-1])
# print(prefix)
for i in range(0,q):
 x=int(input())
 print(prefix[(x-1)%(n+1)])


from math import *
from collections import *
from itertools import *
from functools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(100000000)

n,k=map(int,input().split())
l=list(map(int,input().split()))
l.append(reduce(xor,l))
l=list(accumulate(l,xor))
for _ in range(k):
 v=int(input())
 print(l[(v-1)%len(l)]) 

from math import *
from collections import *
from itertools import *
from functools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(100000000)

n,k=map(int,input().split())
l=list(map(int,input().split()))
l.append(reduce(xor,l))
l=list(accumulate(l,xor))
for _ in range(k):
 v=int(input())
 print(l[(v-1)%len(l)]) 

# cook your dish here
a = [int(s) for s in input().split()]
b = [int(s) for s in input().split()]
c = [0]
d = 0
for e in range(a[0]):
 d = d ^ b[e]
 c.append(d)
for j in range(a[1]):
 e = int(input())
 if(e <= a[0]): print(c[e])
 else: print(c[(e - (a[0] + 1)) % (a[0] + 1)])

n,q=list(map(int,input().split()))
l=list(map(int,input().split()))
v=[0 for x in range(n)]
v[0]=l[0]
for j in range(1,n):
 v[j]=v[j-1]^l[j]
for i in range(q):
 k=int(input())
 if k<=n:
  print(v[k-1])
 else:
  ans=(k-n)%(n+1)-1
  if ans==0:
   print(0)
  elif ans<0:
   print(v[n-1])
  else:
   print(v[ans-1])


n,q = map(int,input().split())
f = list(map(int,input().split()))
l = [0,f[0]]
for i in range(1,n,1):
 l.append(l[-1]^f[i])
l.append(0)
for _ in range(q):
 a = int(input())
 print(l[a%(n+1)])

# cook your dish here
l=input().split()
n=int(l[0])
q=int(l[1])
l=input().split()
li=[int(i) for i in l]
xori=0
si=[0 for i in range(n)]
for i in range(n):
 si[i]=xori
 xori=xori^li[i]
si.append(xori)
fi=list(li)
fi.append(xori)
for you in range(q):
 q1=int(input())
 print(si[q1%(n+1)])

# cook your dish here
n,q = list(map(int,input().split()))

a = list(map(int,input().split()))
s = [0]*(n+1)
for i in range(n):
 if i==0:
  s[i] = a[i]
 else:
  s[i] = s[i-1]^a[i]
s[n] = 0
for _ in range(q):
 k = int(input())
 k-=1
 k = k%(n+1)
 print(s[k])

# cook your dish here

n, q = [int(a) for a in input().strip().split()]

F = [int(a) for a in input().strip().split()]

S = [0]

for i in range(n):
 S.append(S[i] ^ F[i])

for _ in range(q):
 k = int(input())
 print(S[k%(n+1)])

# cook your dish here
nums = list(map(int, input().split()))

arr = list(map(int, input().split()))

count = 0
s = []

for item in arr:
 
 count = count ^ item
 s.append(count)
 
for i in range(nums[1]):
 query = int(input())
 
 if query % (nums[0] + 1) == 0:
  print(0)
 else:
  print(s[query % (nums[0] + 1) - 1])


# cook your dish here
n, q = map(int, input().split(' '))

n_bonacci = list(map(int, input().split(' ')))
arr = []
xor = 0
for val in n_bonacci:
 xor = xor ^ val
 arr.append(xor)

for query in range(q):
 s = int(input())
 
 if s % (n + 1) == 0:
  print(0)
 else:
  print(arr[s % (n + 1) - 1])

n,q = list(map(int, input().split()))
F = []
S = []
line1 = input().split()
last = 0
for i in range(n):
 F.append(int(line1[i]))
 last = last^int(line1[i])
 S.append(last)
S.append(0)

for i in range(q):
 query = int(input())
 pos = (query-1) % len(S)
 final = S[pos]
 print(final)


n,q=list(map(int,input().split()))
arr=[int(n) for n in input().split()]
x=arr[0]
arr1=[]
arr1.append(x)
for i in range(1,n):
 x=x^arr[i]
 arr1.append(x)
arr1.append(0)
while(q):
 q=q-1
 x=int(input())
 r=x%(n+1)
 print(arr1[r-1])
 


n,q=map(int,input().split())
a=list(map(int,input().split()))
xor=0
sl=[]
for i in a:

 xor=xor^i
 sl.append(xor)
for i in range(q):
 qval=int(input())
 if(qval%(n+1)==0):
  print(0)
 else:
  print(sl[qval%(n+1)-1])

n,q = map(int,input().split())
f = [int(w) for w in input().split()]

ft = []

ft.append(f[0])

for i in range(1,n):
 temp = ft[i-1]
 temp = temp ^ f[i]
 ft.append(temp)
ft.append(0)

while (q):
 k = int(input())
 index = k%(n+1) - 1
 print(ft[index])
 q = q - 1

#Afrikavi

nq = [x for x in list(map(int, input().split(' ')))]
tab = [x for x in list(map(int, input().split(' ')))]
xs = tab[0]
sol = []
sol.append(tab[0])
for i in range(1, nq[0]):
 xs ^= tab[i]
 sol.append(xs)
sol.append(sol[-1] ^ xs)
#print(sol)
for i in range(nq[1]):
 q = int(input())
 print(sol[(q - 1) % (nq[0] + 1)])


n,q=map(int,input().split())
f=list(map(int,input().split()))
for j in range(1,n):
 f[j]^=f[j-1]
#print(f)
for g in range(q):
 k=int(input())
 tyagibagi=k%(n+1)
 if tyagibagi==0:
  print(0)
 else:
  print(f[tyagibagi-1])

n,q=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
xor=a[0]
for i in range(1,len(a)):
 xor = xor^a[i]
a.append(xor)
#q=int(input())
s = [a[0]]
for i in range(1, len(a)):
 s.append(s[-1] ^ a[i])
for I in range(q):
 k=int(input())
 k-=1
 print(s[(k)%(n + 1)])