Добравшись до лагеря, Мэнни и Сид нашли в нём массив чисел. Тогда они захотели с его помощью сыграть в игру. Они в каком-то порядке будут подходить к массиву и проделывать с ним операции.
Когда Мэнни подходит к массиву, он может поменять значение одного элемента в нём на любое другое. Когда Сид подходит к массиву, он выбирает два числа a и b (1 ≤ a ≤ b ≤ n). После этого, для всех возможных l и r, таких что a ≤ l ≤ r ≤ b, он возьмёт подотрезок массива от элемента с номером l до элемента с номером r (включительно), посчитает xor (побитовое исключающее ИЛИ) его элементов, и вычислит сумму всех полученных чисел.
Однако, друзьям нужно продолжать путь, и у них нет времени на игры. Как всем известно, у мамонтов идеальная память. Поэтому Мэнни запомнил найденный ими массив и все ходы, которые они собирались сделать в игре, и решил сыграть в эту игру по пути. Помогите ему определить, какие числа получил бы Сид на своих ходах.
В первой строке даны два целых числа n и m (1 ≤ n, m ≤ 10^5
) - длина массива и количество ходов в игре. В следующей строке даны n целых чисел v[i]
(0 ≤ v[i]
≤ 10^8
) - изначальный массив.
В следующих m строках дано по три числа - описание ходов.
1 i x - Мэнни поменял значение элемента с номером i на x (1 ≤ i ≤ n, 0 ≤ x ≤ 10^8
).
2 a b - Сид выбрал пару чисел a и b (1 ≤ a ≤ b ≤ n).
Для каждого хода Сида выведите полученную сумму в новой строке.