Джеймс настолько любит апельсины, что он сделал для них сканер, используя 4 камеры икомпьютер Raspberry Pi 3b+, и начал создавать 3D изображения апельсинов. Его процессоризображений не очень хорош, поэтому в результате сканирования он получает только 32-битное целое число, которое содержит информацию о повреждениях на кожуре. 32-битноечисло представляется последовательностью из 32 битов, каждый из которых может бытьнулем или единицей. Если занумеровать биты с 0, то можно получить число D, сложив 2^i
длякаждого i-го бита, равного единице. Более формально, число D задаетсяпоследовательностью d[31]
,d[30]
,.......,d[0]
если D=d[31]
* 2^31
+ d[30]
* 2^30
+....+ d[0]
* 2^0
.Например, число 13 представляется как 0,...,0,1,1,0,1 .Джеймс отсканировал апельсинов; тем не менее иногда он решает пересканировать один изапельсинов (i-й апельсин) во время выполнения вашей программы. Это значит, что послепересканирования нужно использовать новое значение для i-го апельсина.Джеймс хочет анализировать полученные данные. Он считает операцию "исключающего ИЛИ"(XOR) очень интересной, поэтому решает использовать ее в вычислениях. Он выбираетдиапазан апельсинов с l до u (где ) и хочет вычислить результат операции XOR,примененной ко всем числам диапазана, ко всем парам соседних элементов диапазона, всемпоследовательностям 3 из соседних элементов, и т. д. вплоть до последовательности из u-l+1соседних элементов (всех элементов диапазона).То есть, если l = 2, u = 4 и A — массив полученных в результате сканирования значений,программа должна вернуть результат следующего выражения : a[2]
xor a[3]
xor a[4]
xor (a[2]
xor a[3]
) xor (a[3]
xor a[4]
) xor (a[2]
xor a[3]
xor a[4]
) , где a[i]
обозначаетобозначает i-й элемент в массиве A.
#####Операция XOR над двумя числовыми значениями определяется так:Если i-й бит первого числа такой же, как i-й бит второго, то i-й бит результата равен 0; если i-й бит первого числа отличается от i-го бита второго числа, то i-й бит результата равен 1.
В первой строке входных данных расположены 2 целых положительных числа n и q (общее число операций пересканирования и анализа данных).В следующей строке расположены n разделенных пробелом целых неотрицательных чисел, которые представляют значения массива A (результаты сканирования апельсинов). Элемент a[i]
содержит описание i-го апельсина. Индексы нумеруются начиная с 1 . Операции описываются в следующих строках, с помощью трех разделенных пробелами целых положительных чисел.Если операция имеет тип 1 (пересканирование), то первое число равно 1, за ним следует i (индекс апельсина, который хочется пересканировать) и j (результат пересканирования i-гоапельсина).Если тип операции 2 (анализ), первое число равно 2 , за ним следуют l и u .
####Выходные данныеВы должны вывести в точности одно целое число для каждой операции типа 2 (анализданных). Вы должны выводить каждое значени в отдельной строке. Обратите внимание, что i-я строка выходных данных должна соответствовать i-й операции типа .
####Ограничения
a[i]
<= 10^9
0 < n , q <= 2 * 10^5
####Объяснение к первому примеру:В начале 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.