Statement is not available in English language
E. Очень странные операции
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Валеры есть мультимножество неотрицательных целых чисел размера n и q запросов на изменение этого мультимножества. Мультимножество может содержать несколько одинаковых элементов. Запросы бывают трёх типов:

  1. Прибавить 1 ко всем числам в мультимножестве.
  2. Добавить число в мультимножество.
  3. Удалить один экземпляр значения из мультимножества (если таких чисел в мультимножестве нет, ничего делать не нужно).

Валера — большой поклонник битовых операций, в особенности операции побитового исключающего или (xor). Ему очень хочется узнать каким был результат выполнения операции xor для всех элементов мультимножества после каждого изменения.

В программировании Валера не очень силён, поэтому решить эту задачу предстоит вам.

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

В первой строке вводятся два целых числа $$$n$$$, $$$q$$$ $$$(1 \le n, q \le 200 000)$$$ — размер массива $$$a$$$ и количество запросов.

Во второй строке вводится $$$n$$$ целых чисел $$$a_1, a_2, \dotsc , a_n$$$ $$$(0 \le a_i \le 10^{18})$$$ — изначальное мультимножество чисел Валеры.

В следующих $$$q$$$ строках будет информация о запросах по одному на строке. Каждая из них будет начинаться с числа $$$type_i$$$ $$$(1 \le type_i \le 3)$$$ — типа запроса.

Если это запрос второго, или третьего типа, через пробел после типа будет число $$$value_i$$$ $$$(0 \le value_i \le 10^{18})$$$ — значение, которое нужно добавить в мультимножество, если $$$type_i$$$ = 2 и удалить, если $$$type_i$$$ = 3.

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

В $$$i$$$-й строке выведите результат выполнения операции xor для всех чисел в мультимножестве Валеры после первых $$$i$$$ изменений.

Система оценки

Тесты к этой задаче состоят из 3 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.

ГруппаБаллыДоп. ограниченияНеобх. группыКомментарий
$$$n,q$$$$$$a_i$$$
$$$0$$$————Тесты из условия.
$$$1$$$22$$$n,q \le 100$$$—0
$$$2$$$16—$$$a_i \le 100$$$—Нет запросов второго типа
$$$3$$$62——0-2
Пример
Входные данные
5 5
0 1 3 4 4
1
2 0
1
3 7
3 6
Выходные данные
7
7
5
5
3