Последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
nand.in
вывод
nand.out

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

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

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

Входные данные

В первой строке даны два числа n, m, k (1 ≤ n, m ≤ 2·105, 1 ≤ k ≤ 31) — количество чисел в последовательности, число операций и длина числа.

Во второй строке даны n чисел ai (0 ≤ ai ≤ 2k - 1) — исходное состояние последовательности.

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

Для запроса первого типа записаны три числа x y (1 ≤ x ≤ n, 0 ≤ y ≤ 2k - 1) — позиция в последовательности и новое значение.

Для запроса второго типа записаны три числа l r (1 ≤ l ≤ r ≤ n) — левая и правая граница подотрезка, на котором нужно посчитать значение функции.

Выходные данные

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

Примеры тестов

Входные данные
4 4 5
31 0 12 4
2 1 4
2 2 3
1 3 19
2 2 4
Выходные данные
31
31
27