E. Шахтёрское ремесло
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Она создала игровой мир длины $$$n$$$ и бесконечной высоты для экспериментов.

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

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

Данные вам логи игры выглядят как список команд. Команды могут быть двух типов:

  • $$$1$$$ $$$a$$$ $$$b$$$ создаёт в небе линию из $$$b$$$ блоков, начиная с координаты $$$a$$$, если считать от края игрового мира длиной $$$n$$$.
  • $$$2$$$ означает, что Таня проверила статистику движка и узнала число текстур, и вашему модулю нужно посчитать и вывести ожидаемое число текстур травы в текущем состоянии игры.

Гарантируется, что текстуры травы не отрисовываются под землёй, а также на границах игрового мира.

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

В первой строке заданы целые числа $$$n$$$ и $$$q$$$ $$$(1 \le n \le 10^6, \, 1 \le q \le 10^4)$$$ — длина тестового игрового мира и общее количество команд в логах игры.

В следующих $$$q$$$ строках содержатся команды из логов игры:

  • Если команда начинается на $$$1$$$, то следом за ней через пробел заданы целые числа $$$a$$$ и $$$b$$$ $$$(a, \, b \gt 0; \, a + b \le n)$$$ — координата начала линии блоков и длина этой линии блоков.
  • Если команда начинается на $$$2$$$, то больше в этой строке ничего нет.
Выходные данные

В ответ на каждую команду типа $$$2$$$ выведите ожидаемое количество текстур травы, которое должно отображаться в заданном игровом мире в соответствии с внесёнными в него изменениями.

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

Обозначим за $$$x$$$ количество команд второго типа.

ГруппаДоп. ограниченияБаллыНеобх. подгруппы
$$$n$$$$$$b$$$$$$x$$$
$$$1$$$$$$n \le 10^3$$$$$$b = 1$$$$$$x = 1$$$30—
$$$2$$$——$$$x \le \frac{q}{100}$$$30$$$1$$$
$$$3$$$———40$$$1$$$, $$$2$$$
Пример
Входные данные
3 7
2
1 1 2
1 2 2
2
1 1 1
1 3 1
2
Выходные данные
3
5
3
Примечание

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

Команда 1 1 2:

 

Команда 1 2 2: