Свадьба
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня у Филиппа и Авроры свадьба, на которую приглашены все феи Топких Болот. Аврора слегка заскучала и решила понаблюдать за общением фей.

Исходно на свадьбе находится $$$n$$$ фей, Аврора пронумеровала их от $$$1$$$ до $$$n$$$. Фея номер $$$i$$$ характеризуется своей общительностью — целым неотрицательным числом $$$a_i$$$.

За время наблюдения, Аврора видела $$$q$$$ интересных моментов. Во время $$$j$$$-го из них происходило событие одного из трех типов:

  1. На свадьбу приходит фея с общительностью $$$v_j$$$. Аврора назначает ей первый неиспользованный ранее номер. Например, первая пришедшая фея получит номер $$$n + 1$$$, следующая — $$$n + 2$$$ и так далее.
  2. Фея с номером $$$p_j$$$ покидает свадьбу.
  3. На свадьбе объявляется танец, характеризующийся своей экспрессивностью $$$e_j$$$ — целым неотрицательным числом. После танца, общительности всех фей изменяются. Если до танца фея имела общительность $$$b$$$, то после ее общительность станет равна $$$b \oplus e_j$$$, то есть побитовому исключающему ИЛИ чисел $$$b$$$ и $$$e_j$$$.

Аврору очень интересует, насколько интенсивно феи общаются. Для этого она хочет после каждого из событий определять суммарный уровень общительности всех фей, присутствующих на свадьбе. Помогите Авроре справиться с этой нелегкой задачей.

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

В первой строке даны два целых числа $$$n$$$ и $$$q$$$ — количество фей, исходно находящихся на свадьбе, и количество интересных моментов в наблюдении Авроры ($$$1 \le n, q \le 100\,000$$$).

Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ — значения общительности фей, исходно находящихся на свадьбе ($$$1 \le a_i \le 10^9$$$).

В следующих $$$q$$$ строках даны описания интересных моментов. Каждая из них начинается с целого числа $$$t_j$$$ — типа события ($$$t_j \in \{1, 2, 3\}$$$).

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

После каждого события выведите сумму значений общительности всех фей, находящихся на свадьбе.

Пример

Входные данные
6 5
2 3 9 5 6 6
1 3
3 5
2 2
3 2
2 7
Выходные данные
34
37
31
27
23