Участвуя в раскопках гробницы Тутонхамона, фиксики нашли последовательность из n k-битных чисел и руководство к действию. Чтобы открыть таинственную дверь, нужно выполнить последовательность из m операций одного из двух типов:
Функция f(l, r) определяется так:
Помогите фиксикам найти значения, полученные в ходе выполнения всех операций второго типа.
В первой строке даны два числа n, m, k (1 ≤ n, m ≤ 2·105, 1 ≤ k ≤ 31) — количество чисел в последовательности, число операций и длина числа.
Во второй строке даны n чисел ai (0 ≤ ai ≤ 2k - 1) — исходное состояние последовательности.
В следующих m строках даны запросы.
Для запроса первого типа записаны три числа 1 x y (1 ≤ x ≤ n, 0 ≤ y ≤ 2k - 1) — позиция в последовательности и новое значение.
Для запроса второго типа записаны три числа 2 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