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$$$。根本没有火车。