XORanges#9045

XORanges

1 saniyə

128 meqabayt

Çətin

Жанез portağalları çox sevir! Buna görə də o, portağalları skan etmək üçün bir cihaz hazırlayıb. Kamera və Raspberry Pi 3b+ kompüteri vasitəsilə o, portağalların 3D şəkillərini yaratmağa başlayıb. Onun şəkil prosessoru çox güclü deyil, buna görə də o, yalnız qabığın üzərindəki deşiklər haqqında məlumat verən $32$ bitlik tam ədəd alır. Bu $32$ bitlik tam ədəd $D$ , $32$ rəqəmdən (bitdən) ibarət ardıcıllıq şəklində təqdim olunur, hər biri ya bir, ya da sıfırdır. Əgər $0$ -dan başlasaq, hər bir $i$ -ci biti bir olan üçün $2^{i}$ 2^i əlavə edərək ədəd əldə edə bilərik. Daha dəqiq desək, $D$ $d_{31}, d_{30}, ..., d_{0}$ d_{31}, d_{30}, ..., d_0 ardıcıllığı şəklində təqdim olunur, burada $D = d_{31} \cdot 2^{31} + d_{30} \cdot 2^{30} + ... + d_{1} \cdot 2^{1} + d_{0} \cdot 2^{0}$ D = d_{31} \cdot 2^{31} + d_{30} \cdot 2^{30} + ... + d_1 \cdot 2^1 + d_0 \cdot 2^0. Məsələn, $13$ $0, ..., 0, 1, 1, 0, 1$ 0, ..., 0, 1, 1, 0, 1 kimi təqdim olunur.

Жанез $n$ portağalı skan etdi; lakin bəzən o, proqramınızın icrası zamanı bir portağalı ( $i$ -ci portağalı) yenidən skan etməyə qərar verir. Bu o deməkdir ki, bu skanlamadan başlayaraq o, $i$ -ci portağal üçün yenilənmiş dəyəri istifadə edir.

Жанез bu portağalları təhlil etmək istəyir. O, XOR (eksklüziv VƏ YA) əməliyyatını çox maraqlı hesab edir, buna görə də bəzi hesablamalar aparmağa qərar verir. O, $l$ -dən $u$ -ya qədər portağalların bir aralığını seçir (burada $l \leq u$ l \le u) və bu aralıqdakı bütün elementlərin, bu aralıqdakı ardıcıl elementlərin bütün cütlərinin, ardıcıl $3$ elementdən ibarət bütün ardıcıllıqların və s., $u - l + 1$ u - l + 1 ardıcıl elementdən ibarət ardıcıllığa (aralıqdakı bütün elementlərə) qədər olan XOR dəyərini bilmək istəyir.

Əgər $l = 2$ l = 2 və $u = 4$ u = 4-dürsə və skan edilmiş dəyərlərdən ibarət $A$ massivimiz varsa, proqram $a_{2} \oplus a_{3} \oplus a_{4} \oplus (a_{2} \oplus a_{3}) \oplus (a_{3} \oplus a_{4}) \oplus (a_{2} \oplus a_{3} \oplus a_{4})$ a_2 \oplus a_3 \oplus a_4 \oplus (a_2 \oplus a_3) \oplus (a_3 \oplus a_4) \oplus (a_2 \oplus a_3 \oplus a_4) dəyərini qaytarmalıdır, burada $\oplus$ XOR əməliyyatını təmsil edir və $a_{i}$ a_i $A$ massivindəki $i$ -ci elementi təmsil edir.

XOR əməliyyatını belə təyin edək:

Əgər birinci dəyərin $i$ -ci biti ikinci dəyərin $i$ -ci biti ilə üst-üstə düşürsə, nəticənin $i$ -ci biti $0$ -a bərabərdir;
Əgər birinci dəyərin $i$ -ci biti ikinci dəyərin $i$ -ci bitindən fərqlidirsə, nəticənin $i$ -ci biti $1$ -ə bərabərdir.

Məsələn, $13 \oplus 23 = 26$ 13 \oplus 23 = 26.

Giriş

Birinci sətirdə $n$ və $q (0 < n, q \leq 2 \cdot 1 0^{5})$ q~(0 < n, q \le 2 \cdot 10^5) iki müsbət tam ədəd var (ümumi yenidən skan etmə və sorğu — əməliyyatlar sayı).

Növbəti sətirdə $n$ qeyri-mənfi tam ədəd var, bu ədədlər $A$ massivinin dəyərlərini (portağalların skan nəticələrini) təmsil edir. $a_{i} (a_{i} \leq 1 0^{9})$ a_i~(a_i \le 10^9) elementi $i$ -ci portağal üçün dəyəri ehtiva edir. İndeks $i$ $1$ -dən başlayır.

Əməliyyatlar növbəti $q$ sətirdə üç müsbət tam ədəd ilə təsvir olunur.

Əgər əməliyyat tipi $1$ -dirsə (yenidən skan etmə), birinci tam ədəd $1$ -ə bərabərdir, sonra $i$ (Жанезin yenidən skan etmək istədiyi portağalın indeksi) və $j$ (yenidən skan edilmiş $i$ -ci portağalın nəticəsi) gəlir.

Əgər əməliyyat tipi $2$ -dirsə (sorğu), birinci tam ədəd $2$ -ə bərabərdir, sonra $l$ və $u$ gəlir.

Çıxış

Hər bir sorğu üçün ayrı sətirdə bir tam ədəd çıxarın. Qeyd edək ki, çıxışın $i$ -ci sətiri $i$ -ci sorğunun nəticəsinə uyğun olmalıdır.

Nümunələr

Misal 1 üçün izah.

Əvvəlcə $A = [1, 2, 3]$ A = [1, 2, 3]. Birinci sorğu bütün aralığı əhatə edir. Nəticə $1 \oplus 2 \oplus 3 \oplus (1 \oplus 2) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = 2$ 1 \oplus 2 \oplus 3 \oplus (1 \oplus 2) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = 2 olacaq.

Sonra birinci portağalın dəyəri $3$ -ə yenilənir. Bu, eyni sorğu üçün nəticəni dəyişdirir (aralıqda $[1, 3]$ ): $3 \oplus 2 \oplus 3 \oplus (3 \oplus 2) \oplus (2 \oplus 3) \oplus (3 \oplus 2 \oplus 3) = 0$ 3 \oplus 2 \oplus 3 \oplus (3 \oplus 2) \oplus (2 \oplus 3) \oplus (3 \oplus 2 \oplus 3) = 0.

Nümunə 1

Nümunə 2