XORanges

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

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

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

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

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

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

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

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

Вхідні дані

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

У наступному рядку знаходяться $n$ невід’ємних цілих чисел, які представляють значення масиву $A$ (результати сканування апельсинів). Елемент $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]$. Перший запит охоплює весь діапазон. Результатом буде значення $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$.