Гра з масивом#11266

Гра з масивом

2 секунди

512 мегабайтів

Дуже складна

Прибувши до табору, Менні та Сід знайшли масив чисел і вирішили зіграти з ним у гру. Вони по черзі підходять до масиву та виконують певні операції.

Коли Менні підходить до масиву, він може змінити значення одного з елементів на будь-яке інше. Коли Сід підходить до масиву, він обирає два числа $a$ і $b$ ( $1 \leq a \leq b \leq n$ 1 \le a \le b \le n). Потім, для всіх можливих $l$ і $r$ , таких що $a \leq l \leq r \leq b$ a \le l \le r \le b, він бере підмасив від елемента з номером $l$ до елемента з номером $r$ (включно), обчислює $x or$ (побітове виключне АБО) його елементів, і підсумовує всі отримані значення.

Однак, друзям потрібно продовжувати свій шлях, і у них немає часу на ігри. Як відомо, у мамонтів чудова пам'ять. Тому Менні запам'ятав знайдений масив і всі заплановані ходи, щоб зіграти в цю гру в дорозі. Допоможіть йому визначити, які числа отримав би Сід під час своїх ходів.

Вхідні дані

У першому рядку дано два цілих числа $n$ і $m$ ( $1 \leq n, m \leq 1 0^{5}$ 1 \le n, m \le 10^5) - довжина масиву та кількість ходів у грі. У наступному рядку наведено $n$ цілих чисел $v_{i}$ v_i ( $0 \leq v_{i} \leq 1 0^{8}$ 0 \le v_i \le 10^8) - початковий масив.

У наступних $m$ рядках наведено по три числа, що описують ходи:

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

Вихідні дані

Для кожного ходу Сіда виведіть отриману суму в новому рядку.

Приклади

Приклад 1