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