28742번 - Свадьба 다국어

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

Исходно на свадьбе находится $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\}$).

• Если $t_j = 1$, то далее дано целое число $v_j$ --- общительность пришедшей феи ($1 \le v_j \le 10^9$). Пришедшая фея получает первый неиспользованный ранее номер.
• Если $t_j = 2$, то далее дано целое число $p_j$, означающее, что фея с номером $p_j$ покидает свадьбу. Гарантируется, что в этот момент фея с номером $p_j$ присутствовала на свадьбе.
• Если $t_j = 3$, то далее дано целое число $e_j$ --- экспрессивность танца ($1 \le e_j \le 10^9$).

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