Добравшись до лагеря, Мэнни и Сид нашли в нём массив чисел. Тогда они захотели с его помощью сыграть в игру. Они в каком-то порядке будут подходить к массиву и проделывать с ним операции.

Когда Мэнни подходит к массиву, он может поменять значение одного элемента в нём на любое другое. Когда Сид подходит к массиву, он выбирает два числа a и b (1 ≤ a ≤ b ≤ n). После этого, для всех возможных l и r, таких что a ≤ l ≤ r ≤ b, он возьмёт подотрезок массива от элемента с номером l до элемента с номером r (включительно), посчитает xor (побитовое исключающее ИЛИ) его элементов, и вычислит сумму всех полученных чисел.

Однако, друзьям нужно продолжать путь, и у них нет времени на игры. Как всем известно, у мамонтов идеальная память. Поэтому Мэнни запомнил найденный ими массив и все ходы, которые они собирались сделать в игре, и решил сыграть в эту игру по пути. Помогите ему определить, какие числа получил бы Сид на своих ходах.

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

В первой строке даны два целых числа n и m (1 ≤ n, m ≤ 105) - длина массива и количество ходов в игре. В следующей строке даны n целых чисел vi (0 ≤ vi ≤ 108) - изначальный массив.

В следующих m строках дано по три числа - описание ходов.

• 1 i x - Мэнни поменял значение элемента с номером i на x (1 ≤ i ≤ n, 0 ≤ x ≤ 108).
• 2 a b - Сид выбрал пару чисел a и b (1 ≤ a ≤ b ≤ n).

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

Для каждого хода Сида выведите полученную сумму в новой строке.