C. Техническое обслуживание поездов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кавасиро Нитори — талантливый инженер. Поэтому ее назначили ответственной по обслуживанию поездов.

Всего существуют $$$n$$$ моделей поездов, и в депо, в котором работает Нитори, в любой момент времени будет не более одного поезда каждой модели. Изначально в депо нет поездов, и в каждый из следующих $$$m$$$ дней либо один поезд будет добавлен в депо, либо один поезд будет убран из депо. Когда добавляется поезд $$$i$$$-й модели в день $$$t$$$, он будет работать $$$x_i$$$ дней (включая день $$$t$$$), затем будет на ремонте в течение $$$y_i$$$ дней, затем опять работать $$$x_i$$$ дней, и так далее до тех пор, пока его не уберут из депо.

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

В день, когда поезд убирают, он не считается находящимся в ремонте.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$).

Каждая $$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i,y_i$$$ ($$$1 \le x_i,y_i \le 10^9$$$).

Далее следуют $$$m$$$ строк, содержащих два целых числа $$$op$$$ и $$$k$$$ ($$$1 \le k \le n$$$, $$$op = 1$$$ или $$$op = 2$$$). Если $$$op=1$$$, это означает, что в этот день добавляется поезд $$$k$$$-й модели, иначе поезд модели $$$k$$$ убирают. Гарантируется, что когда добавляется поезд модели $$$x$$$, в депо нет поездов такой модели, а когда поезд модели $$$x$$$ убирают, в депо есть такой поезд.

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

Выведите $$$m$$$ строк, каждая $$$i$$$-я из которых содержит одно целое число, обозначающее количество поездов, находящихся на ремонте в $$$i$$$-й день.

Примеры
Входные данные
3 4
10 15
12 10
1 1
1 3
1 1
2 1
2 3
Выходные данные
0
1
0
0
Входные данные
5 4
1 1
10000000 100000000
998244353 1
2 1
1 2
1 5
2 5
1 5
1 1
Выходные данные
0
0
0
1
Примечание

Рассмотрим первый пример.

Первый день: Нитори добавляет поезд модели $$$3$$$. Работает только поезд модели $$$3$$$, и ни один поезд не находится в ремонте.

Второй день: Нитори добавляет поезд модели $$$1$$$, поезд модели $$$1$$$ работает, а поезд модели $$$3$$$ находится в ремонте.

Третий день: Нитори убирает поезд модели $$$1$$$. Ситуация такая же, как и в первый день.

Четвертый день: Нитори убирает поезд модели $$$3$$$. Нет ни одного поезда.