Задача: Испытание силомера
Сайтама выполняет последовательные удары по силомеру. Силомер представляет из себя массив целых чисел длины \(n\). Изначально \(i\)-е число массива равно \(a_i\) для всех \(i\).
Вам необходимо обработать \(q\) событий, происходящих с силомером. Событие номер \(i\) может быть одного из трех типов:
-
подходит наблюдатель и просит посчитать сумму чисел массива на отрезке \([l_i; r_i]\), то есть величину \(a_{l_i} + a_{{l_i}+1} + \ldots + a_{r_i}\);
-
Сайтама наносит обычный удар силы \(x_i\) по отрезку \([l_i; r_i]\): всем элементам массива на позициях от \(l_i\) до \(r_i\) включительно присваивается значение \(x_i\)
-
Сайтама наносит сильный удар по отрезку \([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\)).
Для каждого события первого типа выведите в отдельной строке сумму элементов массива на отрезке, заданном этим событием.
Ваш ответ: