Джеймс настолько любит апельсины, что он сделал для них сканер, используя 4 камеры и компьютер Raspberry Pi 3b+, и начал создавать 3D изображения апельсинов. Его процессор изображений не очень хорош, поэтому в результате сканирования он получает только 32- битное целое число, которое содержит информацию о повреждениях на кожуре. 32-битное число представляется последовательностью из 32 битов, каждый из которых может быть нулем или единицей. Если занумеровать биты с 0, то можно получить число D, сложив 2i для каждого i-го бита, равного единице. Более формально, число D задается последовательностью d31,d30,.......,d0 если D=d31 * 231 + d30 * 230 +....+ d0 * 20. Например, число 13 представляется как 0,...,0,1,1,0,1 . Джеймс отсканировал апельсинов; тем не менее иногда он решает пересканировать один из апельсинов (i-й апельсин) во время выполнения вашей программы. Это значит, что после пересканирования нужно использовать новое значение для i-го апельсина. Джеймс хочет анализировать полученные данные. Он считает операцию "исключающего ИЛИ" (XOR) очень интересной, поэтому решает использовать ее в вычислениях. Он выбирает диапазан апельсинов с l до u (где ) и хочет вычислить результат операции XOR, примененной ко всем числам диапазана, ко всем парам соседних элементов диапазона, всем последовательностям 3 из соседних элементов, и т. д. вплоть до последовательности из u-l+1 соседних элементов (всех элементов диапазона). То есть, если l = 2, u = 4 и A — массив полученных в результате сканирования значений, программа должна вернуть результат следующего выражения : a2 xor a3 xor a4 xor (a2 xor a3) xor (a3 xor a4) xor (a2 xor a3 xor a4) , где ai обозначает обозначает i-й элемент в массиве A.

Операция XOR над двумя числовыми значениями определяется так:

Если i-й бит первого числа такой же, как i-й бит второго, то i-й бит результата равен 0; если i-й бит первого числа отличается от i-го бита второго числа, то i-й бит результата равен 1.

Входные данные:

В первой строке входных данных расположены 2 целых положительных числа n и q (общее число операций пересканирования и анализа данных). В следующей строке расположены n разделенных пробелом целых неотрицательных чисел, которые представляют значения массива A (результаты сканирования апельсинов). Элемент ai содержит описание i-го апельсина. Индексы нумеруются начиная с 1 . Операции описываются в следующих строках, с помощью трех разделенных пробелами целых положительных чисел. Если операция имеет тип 1 (пересканирование), то первое число равно 1, за ним следует i (индекс апельсина, который хочется пересканировать) и j (результат пересканирования i-го апельсина). Если тип операции 2 (анализ), первое число равно 2 , за ним следуют l и u .

Выходные данные

Вы должны вывести в точности одно целое число для каждой операции типа 2 (анализ данных). Вы должны выводить каждое значени в отдельной строке. Обратите внимание, что i-я строка выходных данных должна соответствовать i-й операции типа .

Ограничения

• ai <= 109
• 0 < n , q <= 2 * 105

Объяснение к первому примеру:

В начале A = [1,2,3]. Первая операция производится над полным диапозоном значений. Результат анализа есть 1 xor 2 xor 3 xor (1 xor 2 ) xor (2 xor 3) xor (1 xor 2 xor 3 ) = 2.

Затем значение первого апельсина меняется на 3. Это приводит к изменению результата в операции анлиза всех данных ( в диапазоне [1,3]). 3 xor 2 xor 3 xor (3 xor 2 ) xor (2 xor 3) xor (3 xor 2 xor 3 ) = 0.