Masala #0218

Xotira 16 MB Vaqt 1000 ms
14

XOR

Biz yangicha fibonachchi sonlarining turini ishlab chiqdik, u quyidagicha hosil qilinadi. Avvaliga \(K\) ta son olinadi, demak fibonachchining dastlabki \(K\) ta elementi shular ya’ni quyidagicha:
\(F(1) = a_1,  F(2) = a_2, \space F(3) = a_3, \space\dots\space, \space F(k) = a_k\)
Qolgan elementlari esa o`zidan oldingi K tasining umumiy xoriga teng ya’ni quyidagicha:
\(F(i) = F(i−1) \space\text{xor}\space F(i−2) \space\text{xor}\space F(i-3) \space\text{xor}\space … \space\text{xor}\space F(i-k), \space (\text{qachonki} \space i > k)\)
Demak sizga yangicha Fibonachchi ketma-ketligimiz tushunarli bo`lsa sizning vazifangiz \(L\) va \(R\) oraliqdagi barcha fibonachchi sonlarimizni umumiy xor qiymatini hisoblab berishingiz talab qilinadi ya’ni quyidagicha:
\(F(L) \space\text{xor}\space F(L+1) \space\text{xor}\space F(L+2) \space\text{xor}\space … \space\text{xor}\space F(R-1) \space\text{xor}\space F(R)\)


Kiruvchi ma'lumotlar:

Birinchi qatorda \(K \space (1 \le K \le 10^5)\) butun son fibonachchining dastlabki elementlari soni.

Keyingi \(K\) ta qatorda \(A_i (0 \le A_i \le 10^{18})\) butun sonlar son fibonachchining dastlabki elementlari beriladi.

Keyingi qatorda \(Q (1 \le K \le 10^6)\)  soni so`rovlar soni.

Keyingi \(Q\) ta qatorda \(L\) va \(R (1 \le L \le R \le 10^{18})\) har bir so`rovdagi \(L\) va \(R\)  siz hisoblab berishingiz kerak bo`lgan oraliq.


Chiquvchi ma'lumotlar:

\(Q\) ta alohida qatorda yagona butun \(L\) va \(R\) oraliqdagi biz tuzgan yangi Fibonachchi ketma-ketligining sonlarini umumiy xor qiymatini chiqaring


Misollar
# input.txt output.txt
1
4
1 3 5 7
3
2 2
2 5
1 5
3
1
0
2
5
3 3 4 3 2
4
1 2
1 3
5 6
7 9
0
4
7
4