Masala F
Behruzbek va XOR so‘rovlar
Behruzbek massivlarda XOR operatsiyasini bajarishni juda ham yoqtiradi. Bir kuni uning oldiga do'sti Temur kelib, uzunligi \(n\) bo'lgan \(a\) massiv hamda \([l,r,x,y]\) turdagi \(q\) ta so'rovlar berdi . Har bir so'rov uchun Behruzbekdan \(a[l:r]\) qismida joylashgan va qiymatlari \([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.
Birinchi qatorda bitta butun son mavjud \(t\) \( (1 \le t \le 1000) \) - testlar soni.
Har bir test uchun birinchi qatorida ikkita butun son mavjud \(n,q\) \( (1 \le n,q \le 4\times 10^5 \) ) - \(a\) massiv uzunligi va so'rovlar soni.
Keyingi qatorda \(n\) ta butun sonlar \(a_1,a_2,..,a_n\) \( (1 \le a_1,a_2,..,a_n \le 10^9) \) - \(a\) massiv elementlari kiritiladi.
Keyingi \(q\) ta qatorning har birida \(4\) ta butun son \(l,r,x,y\) \( (1 \le l \le r \le n) \) \( (1 \le x,y \le 10^9) \) kiritiladi.
\(n+q\) umumiy testlar summasi \( 8\cdot 10^5\) dan oshmasligi kafolatlangan.
Har bir so'rov uchun javobni yangi qatorda chop eting.
| # | 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 |
- \(1\)-so'rov \([5, \color{red}{\underline{\bf{1}}} \color{white}, 4, 2, 3] \) massivini oladi. Elementlardan faqat bittasi \([1,1]\) oralig'ida. Javob: \(1\).
- \(2\)-so'rov \([ \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]\) diapazonni oladi. Javob: \(5 ⊕1 ⊕ 4 ⊕ 2 ⊕ 3 = 1\).
- \(3\)-so'rov \( [ \color{red}{\underline{\bf{5}}} \color{while}{,} 1 , \color{red}{\underline{\bf{4}}} \color{while}{]} \) pastki qator (subarray) va \([2, 100]\) oraliqni oladi. Javob: \(5 ⊕ 4 = 1\).
- \(4\)-so'rov \( [ 1 , \color{red}{\underline{\bf{4}}} \color{while}{]}\) pastki qator (subarray) va \( [2,100] \) diapazonni oladi. Javob: \(4\).
Telegram kanalimizga obuna bo'ling