Во дворе Евстиграфа совсем недавно была генеральная уборка — все жильцы дома собирали листву, подметали дорожки, убирали мусор, который каким-то образом оказался в их чистом дворе. Всё собранное добро они разложили по мешкам и оставили на ночь. Но на следующие утро обнаружилось, что кто-то украл весь мусор (наверное, автор этой задачи).
Единственное, что осталось от всего былого богатства — какой-то странный прибор, на котором написано «УсТнЫй СчЁт 3000». Его явно оставил вор в качестве подсказки к тому, как его найти. Чтобы получить хоть какую-то информацию о личности вора, вам придется сначала разобраться с этим прибором.
Как следует из названия, испытание заключается в проверке ваших навыков устного счёта. Для этого вам сначала показывается массив $$$[a_1, \ldots, a_n]$$$, после чего прибор требует проделать некоторые манипуляции над отрезками массива:
Вы — единственный, кто может помочь Евстиграфу с этой задачей. Но будьте осторожны: от вора мусора можно ожидать неприятные задачи.
В первой строке записаны два числа $$$n$$$ и $$$m$$$ — количество элементов в массиве и количество запросов ($$$1 \leqslant n, m \leqslant 10^5$$$).
В следующей строке записаны $$$n$$$ чисел $$$a_1$$$, ..., $$$a_n$$$ — массив, который показывает прибор ($$$0 \leqslant a_i < 2^{15}$$$).
Следующие $$$m$$$ строк содержат описания запросов:
В каждом запросе выполняется $$$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