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$).

출력

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

제한

힌트