Вам задан массив из $n$ элементов, содержащий $b$-битные неотрицательные числа.

На вход поступают $q$ запросов двух видов:

• set i x - присвоить элементу под индексом $i$ значение $x$.
• get l r - применить к битовому представлению каждого числа на отрезке от $l$ до $r$ произвольную перестановку длиной $b$, и посчитать максимально возможный XOR (побитовое исключащее ИЛИ) этого отрезка, который может после этого получиться.

Обратите внимание:

• после каждого запроса типа get массив возвращается в исходное состояние
• вы выбираете одну и ту же перестановку для всех чисел в запросе, а не отдельную для каждого числа

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

В первой строке записаны числа $n$, $q$ и $b$ - длина массива, количество запросов и битность элементов соответственно ($1 \le n, q \le 2 \cdot 10^5$, $1 \le b \le 32$).

В следующей строке записаны элементы массива. Каждое число находится в диапазоне от $0$ включительно до $2^b$ невключительно.

В каждой из следующих строк записаны запросы в формате из условия ($1 \le l \le r \le n$, $1 \le i \le n$, $1 \le x < 2^b$).

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

В ответ на каждый запрос типа get выведите ответ на него с новой строки.

Подзадачи