28676번 - Игра с массивом 다국어

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

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

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

В первой строке даны два целых числа $n$ и $m$ --- длина массива и количество ходов в игре ($1 \le n, m \le {10}^5$). В следующей строке даны $n$ целых чисел $v_i$ --- изначальный массив ($0 \le v_i \le {10}^8$).

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

• 1 $i$ $x$ --- Мэнни поменял значение элемента с номером $i$ на $x$ ($1 \le i \le n$, $0 \le x \le {10}^8$).
• 2 $a$ $b$ --- Сид выбрал пару чисел $a$ и $b$ ($1 \le a \le b \le n$).

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