Hotel

时间限制：3 秒 / 内存限制：64 MB

Description

火山经营着一个停车场，假设的停车场有 $N$ 车位（编号 $1-N$）都在一条线上，最初所有车位都没停车。经常有人来定车位， 他要定连续的 $k(1 ≤ k ≤ N)$ 个车位。火山要确定是否能够满足客人的要求，如果能，他要将这 $k$ 个连续的车位安排在编 号最小的地方停下。若不能，则客人不停在火山的停车场。在某一时间，有些车会被车主开走了。火山的停车场很大， 火山想让学弟学妹写个程序帮助他。

Input

• 第 $1$ 行输入 $N$ 和 $M$。$N$ 是车位个数，$M$ 表示总操作次数。$1\leq N,M <= 5 \times 10^4$

  接下来 $M$ 行，先输入操作类型 $(1或2)$

• 若是 $1$，表示有人来停车，再输入 $1\leq k\leq n$。

• 若是 $2$，再输入 $l,r$, 表示区间 $[l,r]$ 的车被开走了。$1\leq l\leq r\leq n$。

Output

• 当输入为 $1$ 时，若火山的停车场有连续的 $k$ 个车位，那么输出第一辆车停的最小的编号，否则输出 $0$。

Example

Sample Input

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

Sample Output

1
4
7
0
0