木材

题目描述

有一根长度为 $L$ 米的直线木材。
对于 $x = 1, 2, \dots, L-1$，在距离木材左端 $x$ 米的位置上画有标记线 $x$。

现在有 $Q$ 个操作，第 $i$ 个操作由一对数 $(c_i, x_i)$ 表示。
请按照 $i$ 的升序依次处理每个操作，具体如下：

• 当 $c_i = 1$ 时：在标记线 $x_i$ 处将木材切成两段。
• 当 $c_i = 2$ 时：选择包含标记线 $x_i$ 的那段木材，并输出其长度。

并且对于所有 $c_i = 1, 2$，保证在处理该操作时，标记线 $x_i$ 尚未被切割过。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

对于每一个 $c_i = 2$ 的操作，输出一行结果。第 $j$ 行输出第 $j$ 个此类操作的答案。

输入输出样例 #1

输入 #1

5 3
2 2
1 3
2 2

输出 #1

5
3

输入输出样例 #2

输入 #2

5 3
1 2
1 4
2 3

输出 #2

2

输入输出样例 #3

输入 #3

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

输出 #3

69
31
6
38
38

说明/提示

数据范围

• $1 \leq L \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $c_i = 1$ 或 $2$，$1 \leq i \leq Q$
• $1 \leq x_i \leq L-1$，$1 \leq i \leq Q$
• 对于所有 $i$，不存在 $1 \leq j < i$ 使得 $(c_j, x_j) = (1, x_i)$。
• 所有输入均为整数。

样例解释 1

第 1 个操作时，木材尚未被切割，包含标记线 $2$ 的木材长度为 $5$ 米，因此输出 $5$。
第 2 个操作后，木材被分成长度为 $3$ 米和 $2$ 米的两段。
第 3 个操作时，包含标记线 $2$ 的木材长度为 $3$ 米，因此输出 $3$。