28509번 - Пропал мусор 다국어

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

Единственное, что осталось от всего былого богатства --- какой-то странный прибор, на котором написано <<УсТнЫй СчЁт 3000>>. Его явно оставил вор в качестве подсказки к тому, как его найти. Чтобы получить хоть какую-то информацию о личности вора, вам придется сначала разобраться с этим прибором.

Как следует из названия, испытание заключается в проверке ваших навыков устного счёта. Для этого вам сначала показывается массив $[a_1, \ldots, a_n]$, после чего прибор требует проделать некоторые манипуляции над отрезками массива:

1. Вычислить сумму $\sum\limits_{i = l}^{r} a_i \oplus i$, где $x \oplus y$ --- XOR двух чисел.
2. Присвоить всем элементам массива на отрезке $[l; r]$ значение $x$.
3. Применить ко всем числам на отрезке $[l; r]$ операцию побитового AND, OR или XOR с числом $x$.

Вы --- единственный, кто может помочь Евстиграфу с этой задачей. Но будьте осторожны: от вора мусора можно ожидать неприятные задачи.

В первой строке записаны два числа $n$ и $m$ --- количество элементов в массиве и количество запросов ($1 \leqslant n, m \leqslant 10^5$).

В следующей строке записаны $n$ чисел $a_1$, \ldots, $a_n$ --- массив, который показывает прибор ($0 \leqslant a_i < 2^{15}$).

Следующие $m$ строк содержат описания запросов:

1. запрос первого типа имеет вид <<$1$ $l$ $r$>>;
2. запрос второго типа имеет вид <<$2$ $l$ $r$ $x$>>;
3. запрос третьего типа имеет вид <<$3$ $l$ $r$ $x$ $c$>>, где символ $c$ обозначает, какая логическая операция будет применяться: AND$(\&)$, OR$(|)$ или XOR$(\textasciicircum)$.

В каждом запросе выполняется $1 \leqslant l \leqslant r \leqslant n$ и $0 \leqslant x < 2^{15}$.

Для каждого запроса первого типа выведите в новой строке требуемую сумму.