XORanges#9045

XORanges

1 секунда

128 мегабайтів

Складна

Жанез любить апельсини! Тому він створив сканер для апельсинів. За допомогою камери та комп'ютера Raspberry Pi 3b+ він почав створювати 3D-зображення апельсинів. Його процесор зображень не дуже хороший, тому єдиний вихід, який він отримує, — це $32$ -бітне ціле число, яке містить інформацію про дірки на шкірці. $32$ -бітне ціле число $D$ представлено у вигляді послідовності з $32$ цифр (бітів), кожна з яких є одиницею або нулем. Якщо почати з $0$ , ми можемо отримати число, додаючи $2^{i}$ 2^i для кожного $i$ -го біта, рівного одиниці. Більш формально, число $D$ представлено послідовністю $d_{31}, d_{30}, ..., d_{0}$ d_{31}, d_{30}, ..., d_0, коли $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. Наприклад, $13$ представлено як $0, ..., 0, 1, 1, 0, 1$ 0, ..., 0, 1, 1, 0, 1.

Жанез відсканував $n$ апельсинів; однак іноді він вирішує пересканувати один з апельсинів ( $i$ -й апельсин) під час виконання вашої програми. Це означає, що, починаючи з цього сканування, він використовує оновлене значення для $i$ -го апельсина.

Жанез хоче проаналізувати ці апельсини. Він знаходить операцію виключного АБО (XOR) дуже цікавою, тому вирішує зробити деякі обчислення. Він вибирає діапазон апельсинів від $l$ до $u$ (де $l \leq u$ l \le u) і хоче дізнатися значення XOR всіх елементів у цьому діапазоні, всіх пар послідовних елементів у цьому діапазоні, всіх послідовностей з $3$ послідовних елементів і так далі, аж до послідовності з $u - l + 1$ u - l + 1 послідовних елементів (усіх елементів у діапазоні).

Якщо $l = 2$ l = 2 і $u = 4$ u = 4, і є масив відсканованих значень $A$ , програма повинна повернути значення $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), де $\oplus$ представляє операцію XOR, а $a_{i}$ a_i представляє $i$ -й елемент у масиві $A$ .

Визначимо операцію XOR як:

Якщо $i$ -й біт першого значення збігається з $i$ -м бітом другого значення, то $i$ -й біт результату дорівнює $0$ ;
Якщо $i$ -й біт першого значення відрізняється від $i$ -го біта другого значення, то $i$ -й біт результату дорівнює $1$ .

Наприклад, $13 \oplus 23 = 26$ 13 \oplus 23 = 26.

Вхідні дані

У першому рядку знаходяться $2$ додатні цілі числа $n$ і $q (0 < n, q \leq 2 \cdot 1 0^{5})$ q~(0 < n, q \le 2 \cdot 10^5) (загальна кількість пересканувань і запитів — дій).

У наступному рядку знаходяться $n$ невід'ємних цілих чисел, які представляють значення масиву $A$ (результати сканування апельсинів). Елемент $a_{i} (a_{i} \leq 1 0^{9})$ a_i~(a_i \le 10^9) містить значення для $i$ -го апельсина. Індекс $i$ починається з $1$ .

Дії описані в наступних $q$ рядках з трьома додатними цілими числами.

Якщо тип дії $1$ (пересканування), перше ціле число дорівнює $1$ , за ним слідує $i$ (індекс апельсина, який Жанез хоче пересканувати) і $j$ (результат пересканування $i$ -го апельсина).

Якщо тип дії $2$ (запит), перше ціле число дорівнює $2$ , за ним слідують $l$ і $u$ .

Вихідні дані

Виведіть для кожного запиту одне ціле число в окремому рядку. Зверніть увагу, що $i$ -й рядок виводу повинен відповідати результату $i$ -го запиту.

Приклади

Пояснення до прикладу 1.

Спочатку $A = [1, 2, 3]$ A = [1, 2, 3]. Перший запит охоплює весь діапазон. Результатом буде значення $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.

Потім значення першого апельсина оновлюється до $3$ . Це призводить до зміни результату для того ж запиту (на діапазоні $[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.

Приклад 1

Приклад 2