29034번 - Последовательность 다국어

문제

Участвуя в раскопках гробницы Тутонхамона, фиксики нашли последовательность из $n$ $k$-битных чисел и руководство к действию. Чтобы открыть таинственную дверь, нужно выполнить последовательность из $m$ операций одного из двух типов:

• 1ドル,円x,円y$ --- поменять число в позиции $x$ на число $y$;
• 2ドル,円l,円r$ --- посчитать значение функции $f(l, r)$.

Функция $f(l, r)$ определяется так:

• $f(l, l) = a_l$;
• $f(l, r) = !(f(l, r-1)$ \& $a_r),ドル где ! --- операция побитового отрицания числа, а & --- операция побитового И двух чисел.

Помогите фиксикам найти значения, полученные в ходе выполнения всех операций второго типа.

입력

В первой строке даны два числа $n, m, k$ (1ドル \le n, m \le 2 \cdot 10^5, 1 \le k \le 31$) --- количество чисел в последовательности, число операций и длина числа.

Во второй строке даны $n$ чисел $a_i$ (0ドル \le a_i \le 2^k-1$) --- исходное состояние последовательности.

В следующих $m$ строках даны запросы.

Для запроса первого типа записаны три числа 1ドル,円x,円y$ (1ドル \le x \le n, 0 \le y \le 2^k-1$) --- позиция в последовательности и новое значение.

Для запроса второго типа записаны три числа 2ドル,円l,円r$ (1ドル \le l \le r \le n$) --- левая и правая граница подотрезка, на котором нужно посчитать значение функции.

출력

Для каждого запроса второго типа выведите одно целое число --- результат применения операции на этом отрезке.

제한

힌트