P17627 过期的命令
题目背景
已经过期的命令，没有必要遵守。
项链是我给她的。既然已经用不上了，我应该有权收回那条项链。
「我想问一下当作参考，我还给你之后会怎样？」
「我会把项链丢掉，跟你就此结束。」
「结束是什么意思？」
她像是现在才第一次听说般，问起这个理论上她应该知道的事情。
「我不会再跟你见面。」
「你要是和宇都宫念同一所大学，我们随时都能见面耶。即使如此也一样？」
「我们一开始就约好只到毕业典礼啊。就算随时都能见面，我也不会跟你见面。把项链还我啦。」
「还给你的话，你会丢掉吧？未免太浪费了。」
真不干脆。
她应该早就知道我今天会说些什么了，我们也约好只到毕业典礼为止。尽管事先没有连要将项链还给我这件事都讲定，但这并非需要抗拒的事情。把这种宛如项圈的东西给丢掉，对她来说也是好事才对。
「一点都不浪费。还给我。」
我像是在催促她似的伸出手。
「你这个人真的很小气耶。」
这样说完后，仙台同学夸张地叹了口气。
随即缓缓地解开项链。
「拿去。」
她将项链放在桌上。
我把手伸向银色的项链，然而在碰到之前，仙台同学开了口：「不过在那之前──」
「我有东西想给你看，所以你等一下。」
「有东西想让我看？」
「没错。」
仙台同学一边说：「就是这个。」一边从书包里抽出某个东西，放到项链旁边。
「……信？」
题目描述
**建议阅读样例解释以更好地理解题意。**
宫城眼前的信是一条长度为 $n$ 的纸条，被平铺在数轴上，覆盖了区间 $[0, n]$。
接下来她要对这张纸条进行 $m$ 次折叠操作，对于第 $i$ 次折叠，她会给定两个参数 $p_i,l_i$。
设当前最小的被纸条覆盖的点为 $k$。
- 若 $p_i=1$，以点 $(k+l_i)$ 的位置为折点，将纸条在数轴上小于 $(k+l_i)$ 的部分折向右边。
- 若 $p_i=2$，以点 $(k+l_i)$ 的位置为折点，将纸条在数轴上大于 $(k+l_i)$ 的部分折向左边。
每次折叠操作后，宫城都想知道纸条的最大层数。形式化地，纸条层数是指在数轴上所有形如 $(x+0.5)$ 的点（$x$ 为整数）中，被该纸条覆盖的最大厚度。
输入格式
第一行，两个数，$n$ 和 $m$，表示纸条长度和操作次数。
接下来的 $m$ 行，每行两个数，第 $i$ 行的为 $p_i$ 和 $l_i$，代表第 $i$ 次折叠操作，含义见题目描述。
输出格式
共 $m$ 行，每行一个数，其中第 $i$ 行的表示在第 $i$ 次操作后，数轴上的点最多被纸条覆盖了几层。
说明/提示
#### 样例解释：
对于第一组样例：
所有操作前，被覆盖的位置为 $[0.5,1.5,2.5,3.5]$，层数均为 $1$。纸条覆盖数轴长度为 $4$。
第二次操作前，被覆盖的位置为 $[2.5,3.5]$，层数均为 $2$。纸条覆盖数轴长度为 $2$。
所有操作结束时，被覆盖的位置为 $[2.5]$，层数均为 $4$。纸条覆盖数轴长度为 $1$。
---
对于第二组样例前 $4$ 个操作，每次操作前，纸条在数轴上的覆盖情况依次如下：
层数为 $1$，纸条覆盖数轴长度为 $6$。
层数为 $2$，纸条覆盖数轴长度为 $4$。
层数为 $2$，纸条覆盖数轴长度为 $4$。
层数为 $2$，纸条覆盖数轴长度为 $3$。
---
#### 数据范围：
**本题目采用子任务捆绑测试。**
对于所有数据：$1 \le n\le 5 \times 10^6$，$1 \le m \le 5 \times 10^5$。
- $\forall 1 \le i \le m$，有 $p_i \in \{1,2\}$，$l_i \ge 0$，且 $l_i$ 小于等于操作时纸条覆盖数轴的长度。
::cute-table{tuack}
| 子任务编号 | $n\le$ | $m\le$ | 特殊性质 | 分值 |
|:-:|:-:|:-:|:-:|:-:|
| $0$ | $10$ | $10$ | 无 | $5$ |
| $1$ | $5000$ | $5000$ | ^ | ^ |
| $2$ | $2 \times 10^4$ | $10^4$ | ^ | ^ |
| $3$ | $5 \times 10^5$ | $10^5$ | AB | ^ |
| $4$ | ^ | ^ | A | ^ |
| $5$ | $5 \times 10^6$ | ^ | C | ^ |
| $6$ | ^ | $5 \times 10^5$ | 无 | $20$ |
特殊性质 A：$\forall 1 \le i \le m$，有 $l_i=1$。
特殊性质 B：$\forall 1 \le i \le m$，有 $p_i=2$。
特殊性质 C：数据随机生成。具体的，对于所有的 $1 \le i \le m$，$p_i$ 在 $\{1,2\}$ 中等概率选取，设当前纸条覆盖长度为 $L$，$l_i$ 在 $[0,L]$ 中的所有整数中等概率选取。