题目描述

一个游戏体验区有 $N$ 个座位，编号为 $1$ 到 $N$。开始时，所有座位都是空闲的。管理员需要依次处理 $M$ 条指令。

指令分为以下两种：

• 1 x：为一批玩家安排连续的 $x$ 个空闲座位。如果有多段位置符合要求，选择起始编号最小的一段，并将这 $x$ 个座位标记为已使用。如果不存在符合要求的位置，则不改变任何座位的状态。
• 2 p x：将编号从 $p$ 到 $p+x-1$ 的 $x$ 个座位标记为空闲。需要标记的座位中可能有些本来就是空闲的。

对于每条第一种指令，请输出安排的第一个座位编号；如果无法安排，则输出 $0$。

输入格式

第一行包含两个整数 $N,M$，表示座位数量和指令数量。

接下来 $M$ 行，每行包含一条指令：

• 第一种指令包含两个整数 $1,x$。
• 第二种指令包含三个整数 $2,p,x$。

输出格式

对于每条第一种指令输出一行，表示安排的第一个座位编号。如果无法安排，输出 $0$。

第二种指令不需要输出。

样例

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

1
6
0
3

样例解释

前两条指令分别使用了编号 $1$ 到 $5$、编号 $6$ 到 $7$ 的座位。此时没有连续 $5$ 个空闲座位，因此第三条指令输出 $0$。将编号 $3$ 到 $7$ 的座位标记为空闲后，最后一条指令从编号 $3$ 的座位开始安排。

20 10
1 15
1 6
2 5 10
1 4
1 8
1 2
1 2
1 2
2 3 5
1 5

1
0
5
0
9
11
13
3

100 30
1 13
1 14
1 19
2 41 16
1 10
2 24 11
1 17
1 12
2 76 10
1 1
1 4
2 1 9
1 5
2 39 20
1 2
2 66 4
2 79 12
2 8 9
1 15
2 1 7
2 46 15
1 8
1 13
1 1
1 12
2 73 14
2 37 20
2 69 15
1 12
1 11

1
14
28
41
51
68
24
25
1
6
39
1
46
9
76
37
66

数据范围与提示

• 对于 $10\%$ 的数据，$1 \le N \le 1000$，$1 \le M \le 2000$。
• 对于另外 $10\%$ 的数据，$1 \le N \le 10^4$，$1 \le M \le 2000$。
• 对于 $100\%$ 的数据，$1 \le N,M \le 5\times 10^4$。
• 对于第二种指令，$1 \le p \le p+x-1 \le N$。