XOR so'rovlari

$n$ ta manfiy bo'lmagan butun son va $q$ ta so'rov berilgan. Har bir so'rovda $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$ ni toping, bu yerda $\oplus$ — bitli XOR.

Birinchi qatorda $n$ va $q$ ($1 \le n, q \le 2 \cdot 10^5$). Ikkinchi qatorda $n$ ta butun son ($0 \le a_i \le 10^9$). Keyingi $q$ ta qatorning har birida so'rov: ikkita butun son $l$ va $r$ ($1 \le l \le r \le n$).

Har bir so'rov uchun alohida qatorda bitta son.

XOR ham prefiks bilan ishlaydi, chunki $x \oplus x = 0$: $p_i = a_1 \oplus \ldots \oplus a_i$ bo'lsa, javob $p_r \oplus p_{l-1}$ — umumiy boshlang'ich qism o'zini o'zi yo'q qiladi. Ayirish o'rnini XOR egallaydi.

Misolning birinchi so'rovi: $2 \oplus 4 \oplus 5 = 3$.

Manba: CSES, 1650-masala.