切割木材

题目描述

有一根长度为 $L$ 米的木材。

对于每个 $x=1,2,\dots,L-1$，在距离木材左端 $x$ 米处有一个名为 Mark $x$ 的标记。

给定 $Q$ 个查询，第 $i$ 个查询由一对数 $(c_i,x_i)$ 表示。

按 $i$ 的升序处理查询，处理方式如下。

如果 $c_i=1$：在 Mark $x_i$ 处把木材切成两段。

如果 $c_i=2$：选择包含 Mark $x_i$ 的那段木材，输出它的长度。

这里，对于两种查询 $c_i=1,2$，都保证在处理该查询时，Mark $x_i$ 处还没有被切割过。

输入格式

输入按以下格式从标准输入给出：

$L$ $Q$
$c_1$ $x_1$
$c_2$ $x_2$
$\vdots$
$c_Q$ $x_Q$

输出格式

输出的行数等于 $c_i=2$ 的查询个数。 在第 $j$ 行输出第 $j$ 个此类查询的答案。

样例

5 3
2 2
1 3
2 2

5
3

处理第一个查询时还没有切割，包含 Mark $2$ 的木材长度为 $5$ 米，因此输出 $5$。

第二个查询把木材切成两段，长度分别为 $3$ 米和 $2$ 米。

处理第三个查询时，包含 Mark $2$ 的木材长度为 $3$ 米，因此输出 $3$。

5 3
1 2
1 4
2 3

2

100 10
1 31
2 41
1 59
2 26
1 53
2 58
1 97
2 93
1 23
2 84

69
31
6
38
38

数据范围

• $1 \le L \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• $c_i=1,2$ $(1 \le i \le Q)$
• $1 \le x_i \le L-1$ $(1 \le i \le Q)$
• 对于每个 $i$ $(1 \le i \le Q)$，不存在 $j$ 使得 $1 \le j \lt i$ 且 $(c_j,x_j)=(1,x_i)$。
• 输入中的所有值均为整数。