题目描述

翁老师给你一个长度为 $L$ 的序列。初始这个序列的所有元素分别是 $1,2,3,\cdots,L$。

现在有 $q$ 次操作，分为以下两种。

• 操作一：给定一个数字 $x$，将 $x$ 所在的区间 $[l,r]$ 分裂为 $[l,x]$ 和 $[x+1,r]$。
• 操作二：给定一个数字 $x$，你需要求出 $x$ 所在区间的长度。

具体可以参考样例解释。

输入格式

第一行输入两个整数 $L$ 和 $q$

接下来 $q$ 行每行输入两个整数，第一个整数代表操作类型，第二个整数代表 $x$。

输出格式

输出若干行，每行一个整数代表答案。

5 3
2 2
1 3
2 2

5
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 解释

• 在第一次查询时，还没有进行切割，因此包含数字 $2$ 的区间就是 $[1,5]$ 长度为 $5$ 。
• 在第二次操作中，在位置 $3$ 切割。区间 $[1,5]$ 被分成了 $[1,3]$ 和 $[4,5]$
• 在第三次查询时，包含数字 $2$ 的区间是 $[1,3]$ 区间长度是 $3$ 因此输出了 $3$。

提示

• $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 i \leq Q)$ 都成立：不存在 $j$ ，即 $1 \leq j \lt i$ 和 $(c_j,x_j) = (1, x_i)$ 。
• 所有输入值均为整数。