Испытание силомера
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сайтама выполняет последовательные удары по силомеру. Силомер представляет из себя массив целых чисел длины $$$n$$$. Изначально $$$i$$$-е число массива равно $$$a_i$$$ для всех $$$i$$$.

Вам необходимо обработать $$$q$$$ событий, происходящих с силомером. Событие номер $$$i$$$ может быть одного из трех типов:

  1. подходит наблюдатель и просит посчитать сумму чисел массива на отрезке $$$[l_i; r_i]$$$, то есть величину $$$a_{l_i} + a_{{l_i}+1} + \ldots + a_{r_i}$$$;
  2. Сайтама наносит обычный удар силы $$$x_i$$$ по отрезку $$$[l_i; r_i]$$$: всем элементам массива на позициях от $$$l_i$$$ до $$$r_i$$$ включительно присваивается значение $$$x_i$$$
  3. Сайтама наносит сильный удар по отрезку $$$[l_i; r_i]$$$: для всех $$$j$$$ от $$$l_i$$$ до $$$r_i$$$ включительно происходит присваивание $$$a_j \gets \mathtt{popcount}(a_j)$$$.

Здесь $$$\mathtt{popcount}(x)$$$ — это количество единичных бит в двоичной записи числа $$$x$$$. Иными словами, при событии третьего типа каждое число на отрезке события заменяется на количество своих единичных бит.

На каждый подход наблюдателя, то есть событие первого типа, сообщите ему интересующую его сумму.

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

В первой строке записаны два целых числа $$$n$$$ и $$$q$$$ — длина массива и количество событий ($$$1 \leqslant n, q \leq 2 \cdot 10^5$$$).

Во второй строке через пробел записаны $$$n$$$ целых чисел $$$a_1$$$, ..., $$$a_n$$$ — изначальные элементы массива силомера ($$$0 \leqslant a_i \leqslant 10^9$$$).

Следующие $$$q$$$ строк описывают события. Первое число $$$t_i$$$ в описании события — тип события ($$$1 \leqslant t \leqslant 3$$$). Следующие два заданные через пробел числа — это границы отрезка $$$l_i$$$ и $$$r_i$$$ ($$$1 \leqslant l_i \leqslant r_i \leqslant n$$$). Если это событие второго типа, то есть $$$t_i = 2$$$, далее следует число $$$x_i$$$, обозначающее, что надо выполнить присваивания $$$a_j \gets x_i$$$ для всех $$$l_i \leqslant j \leqslant r_i$$$ ($$$0 \leqslant x_i \leqslant 10^9$$$).

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

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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
112$$$n, q \leqslant 5000$$$полная
27все $$$a_i$$$ и $$$x_i$$$ — степени двойкиполная
34 все $$$a_i$$$ и $$$x_i$$$ — степени двойки или нули 2полная
49$$$t_i \neq 2$$$ для всех $$$i$$$полная
55 для всех событий второго типа $$$l_i = r_i$$$ 4полная
612$$$a_i, x_i \leqslant 20$$$полная
715$$$n \leqslant 10^5$$$ и $$$q \leqslant 10^4$$$1полная
816 все события первого типа следуют строго позже событий второго и третьего типов полная
920нет1 – 8первая ошибка

Примеры

Входные данные
6 6
9 1 3 1 6 3
2 2 3 9
2 4 5 10
3 2 4
1 2 4
1 2 6
3 2 5
Выходные данные
6
19
Входные данные
5 6
0 3 4 1 1
1 2 5
2 2 3 8
3 1 4
3 2 2
1 3 4
2 3 5 5
Выходные данные
9
2