Гра з масивом
Прибувши до табору, Менні та Сід знайшли масив чисел і вирішили зіграти з ним у гру. Вони по черзі підходять до масиву та виконують певні операції.
Коли Менні підходить до масиву, він може змінити значення одного з елементів на будь-яке інше. Коли Сід підходить до масиву, він обирає два числа 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).
Вихідні дані
Для кожного ходу Сіда виведіть отриману суму в новому рядку.