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$) --- левая и правая граница подотрезка, на котором нужно посчитать значение функции.

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