Masala #0218

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)\)

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.

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