XORanges
XORanges
Джеймс настолько любит апельсины, что он сделал для них сканер, используя 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.
3 3 1 2 3 2 1 3 1 1 3 2 1 3
2 0
5 6 1 2 3 4 5 2 1 3 1 1 3 2 1 5 2 4 4 1 1 1 2 4 4
2 5 4 4