Свадьба

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

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

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