410149: GYM103965 C Пропал мусор

C. Пропал мусорограничение по времени на тест3 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

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

Единственное, что осталось от всего былого богатства — какой-то странный прибор, на котором написано «УсТнЫй СчЁт 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$$$, ..., $$$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}$$$.

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

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

ПримерВходные данные

5 6
3 0 11 21 17
1 2 5
2 1 3 9
1 1 4
3 3 5 23 ^
3 2 4 19 &
1 1 5

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

47
46
37