← 返回题目列表

Codeforces · 1580/C

C. 列车维护

中文机器翻译题面 查看原题

Kawasiro Nitori 在工程方面非常出色。因此,她被任命帮助维护火车。

火车有 $$$n$$$ 种型号,而 Nitori 的部门在任何时刻最多只能拥有每种型号的一列火车。一开始没有火车,在接下来的$$$m$$$天,将添加一列火车,或者删除一列火车。当$$$i$$$模型的列车在$$$t$$$天添加时,它会工作$$$x_i$$$天(包括$$$t$$$天),然后维护$$$y_i$$$天,然后再次工作$$$x_i$$$天,依此类推,直到被删除。

为了方便管理,Nitori希望你帮她计算一下每天有多少趟列车在维修。

火车被拆除的那天,不计入维护。

输入

第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$)。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$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$$$天维护的列车数量。

示例

输入 #1

3 4
10 15
12 10
1 1
1 3
1 1
2 1
2 3

输出 #1

0
1
0
0

输入 #2

5 4
1 1
10000000 100000000
998244353 1
2 1
1 2
1 5
2 5
1 5
1 1

输出 #2

0
0
0
1

注意

考虑第一个示例:

第一天:Nitori 添加一列模型火车$$$3$$$。只有$$$3$$$型号的列车在运行,没有列车处于维护状态。

第二天:Nitori 添加了模型火车 $$$1$$$。型号为$$$1$$$的列车正在运行,型号为$$$3$$$的列车正在维护中。

第三天:Nitori 移除一列模型火车$$$1$$$。情况和第一天一样。

第四天:Nitori 移除一列模型火车$$$3$$$。根本没有火车。