Masala #J4CF3QMZO9

Xotira 512 MB Vaqt 2000 ms
14
Muallif: Hasan Saleh

Behruzbek va XOR so‘rovlar

Behruzbek massivlarda XOR operatsiyasini bajarishni juda ham yoqtiradi. Bir kuni uning oldiga do'sti Temur kelib, uzunligi nn bo'lgan aa massiv hamda [l,r,x,y][l,r,x,y] turdagi  qq ta so'rovlar berdi . Har bir so'rov uchun Behruzbekdan a[l:r]a[l:r] qismida joylashgan va qiymatlari [x,y][x,y] oralig'ida bo'lgan elementlarning XOR ni topishni so'radi. Behruzbek bu muammoni bir o'zi hal qila olmadi, shuning uchun sizdan yordam umid qilmoqda. Unga Temurning barcha savollariga javob berishga yordam bering.


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son mavjud tt (1t1000) (1 \le t \le 1000) - testlar soni.

Har bir test uchun birinchi qatorida ikkita butun son mavjud n,qn,q  (1n,q4×105 (1 \le n,q \le 4\times 10^5 ) -  aa massiv uzunligi va so'rovlar soni.

Keyingi qatorda  nn ta butun sonlar a1,a2,..,ana_1,a_2,..,a_n  (1a1,a2,..,an109) (1 \le a_1,a_2,..,a_n \le 10^9) - aa massiv elementlari kiritiladi.

Keyingi qq  ta qatorning har birida  44 ta butun son l,r,x,yl,r,x,y (1lrn) (1 \le l \le r \le n) (1x,y109) (1 \le x,y \le 10^9) kiritiladi.

n+qn+q umumiy testlar summasi 8105 8\cdot 10^5 dan oshmasligi kafolatlangan.


Chiquvchi ma'lumotlar:

Har bir so'rov uchun javobni yangi qatorda chop eting.


Misollar
# input.txt output.txt
1
1
5 4
5 1 4 2 3
1 5 1 1
1 5 1 100
1 3 2 100
2 3 2 100
1
1
1
4
Izoh:
  1. 11-so'rov [5,1,4,2,3][5, \color{red}{\underline{\bf{1}}} \color{white}, 4, 2, 3] massivini oladi. Elementlardan faqat bittasi [1,1][1,1] oralig'ida. Javob: 11.
  2. 22-so'rov  [5, 1, 4, 2, 3][ \color{red}{\underline{\bf{5}}} \color{while}{,}   \color{red}{\underline{\bf{1}}} \color{while}{,}   \color{red}{\underline{\bf{4}}} \color{while}{,}  \color{red}{\underline{\bf{2}}} \color{while}{,}  \color{red}{\underline{\bf{3}}} \color{white}{]} massiv va [1,100][1, 100] diapazonni oladi. Javob: 51423=15 ⊕1 ⊕ 4 ⊕ 2 ⊕ 3 = 1.
  3. 33-so'rov  [5,1,4] [ \color{red}{\underline{\bf{5}}} \color{while}{,} 1 , \color{red}{\underline{\bf{4}}} \color{while}{]} pastki qator (subarray)  va [2,100][2, 100] oraliqni oladi. Javob: 54=15 ⊕ 4 = 1.
  4. 44-so'rov  [1,4] [ 1 , \color{red}{\underline{\bf{4}}} \color{while}{]} pastki qator (subarray) va [2,100] [2,100] diapazonni oladi. Javob: 44.