P17628 信封的选择

我把画有房子平面图的那张纸对折再对折，放在桌上。 「总之你选一边吧。」 「你说要选，是要选什么？」 其实我不用问也知道，却还是问了她。 「项链和信封，选你喜欢的那一边，我会遵照你的选择去做。如果你选了项链，我就不会再跟你见面，即使看到你也不会搭话。今天就是我们最后一次见面。」 「那我要是选信封呢？」 「你就要和我一起住。」

仙台同学给了宫城 $10^9$ 张纸条，分别编号为 $1, 2, \cdots, 10^9$。纸条的初始长度为 $n$。 最初，所有的纸条都被平铺在数轴上，覆盖了区间 $[0, n]$。 宫城会对这些纸条进行 $m$ 次折叠操作。对于第 $i$ 次操作，她会给定三个参数 $t_i,p_i,l_i$。 设当前最小的被纸条 $t_i$ 覆盖的点为 $k$。 - 若 $p_i=1$，以点 $(k+l_i)$ 的位置为折点，将纸条 $t_i$ 在数轴上小于 $(k+l_i)$ 的部分折向右边。 - 若 $p_i=2$，以点 $(k+l_i)$ 的位置为折点，将纸条 $t_i$ 在数轴上大于 $(k+l_i)$ 的部分折向左边。 每次折叠操作后，宫城都想知道纸条 $t_i$ 的最大层数。形式化地，纸条层数是指在数轴上所有形如 $(x+0.5)$ 的点（$x$ 为整数）中，被该纸条覆盖的最大厚度。

第一行，两个数，$n$ 和 $m$，表示纸条长度和操作次数。 接下来的 $m$ 行，每行三个数，第 $i$ 行的为 $t_i,p_i$ 和 $l_i$，代表第 $i$ 次折叠操作。

共 $m$ 行，每行一个数，其中第 $i$ 行的表示在第 $i$ 次操作后，数轴上的点最多被纸条 $t_i$ 覆盖了几层。

#### 数据范围： **本题目采用子任务捆绑测试。** 对于所有数据：$1 \le n \le 5 \times 10^5$，$1 \le m \le 1.2 \times 10^5$。 - $\forall 1 \le i \le m$，有 $1 \le t_i \le 10^9$，$p_i \in \{1,2\}$，$l_i \ge 0$，且 $l_i$ 小于等于操作时纸条 $t_i$ 覆盖数轴的长度。 ::cute-table{tuack} | 子任务编号 | $n\le$ | $m\le$ | 特殊性质 | 分值 | |:-:|:-:|:-:|:-:|:-:| | $0$ | $5 \times 10^5$ | $1.2 \times 10^5$ | $t_i \le 400$ | $10$ | | $1$ | $2 \times 10^5$ | $5 \times 10^4$ | 无 | $20$ | | $2$ | $5 \times 10^5$ | $1.2 \times 10^5$ | ^ | ^ | --- 松开仙台同学的头发后，她便想转过头来，于是我按住她的头，让她面向前面，不能转过来。 「意思是你选择了信封？」 「你觉得选项链比较好的话，那我就选项链。」 我尽量用一如往常的语气说完后，她抓住我按在她头上的手。 「如果宫城要用四年当一个段落，得好好加油，别留级喽。」 「仙台同学真的老爱说些多余的话耶。」 总觉得这种时候应该还有其他更合适的发言才对。虽然我不知道那是什么，但是叫人家别留级这种话绝对不是现在该说的话。 「你这只手放开啦。我也会放手。」 她这么说着，用力握了一下我按在她头上的那只手，随即放开。无可奈何地照她说的放手后，她转过来面向我，接着理所当然地握住我的手。 「以后我可以叫你志绪理吗？」 「不可以。」 「宫城好小气。」 「仙台同学很啰唆耶。」 听到我的声音，仙台同学嘻嘻笑着。 她真的就会说些多余的话。 不过只有四年。 如果就这点时间，要我跟这样的她共度这段时光也行。 我回握住她就这样牵着我，没有放开的手。