题目描述

游乐城的3D游戏体验区广受喜爱，经常爆满。体验区有 $N$ 个座位（编号 $1\sim N$ ）。排队玩家中，部分玩家结伴，需连续空座一同体验，且玩家体验游戏不同，耗时不同，离座时间各异。

玩家来体验时告知管理员需 $x$ 个座位，管理员从 $1\sim N$ 座位找连续 $x$ 个空座，告知玩家起始座位编号并在系统登记占用。若找不到，玩家先去其他项目，之后再来。若有多段连续 $x$ 个空座，选起始座位编号最小的。玩家体验完离开，管理员登记从编号 $p$ 开始的连续 $x$ 个座位空闲。需编程设计此座位管理系统。

输入格式

• 第一行：输入两个整数 $N$、$M$ ，分别表示座位总数和管理员执行指令数 。
• 接下来 $M$ 行：每行一个指令。指令先读整数 $D$ ，若 $D = 1$ ，表示有玩家来体验，再输入整数 $x$ ，代表结伴玩家数量，系统需找连续 $x$ 个空座起始位置编号；若 $D = 2$ ，表示有玩家离开，接着输入两个整数 $p$、$x$ ，表示从编号 $p$ 开始的连续 $x$ 个座位空出 。

数据范围：对于 $10\%$ 的数据，$1 \leq N \leq 1000$ ，$1 \leq M \leq 2000$ ；对于另外 $10\%$ 的数据，$1 \leq N \leq 10000$ ，$1 \leq M \leq 2000$ ；对于 $100\%$ 的数据，$1 \leq N \leq 50000$ ，$1 \leq M \leq 50000$ 。

输出格式

针对每个 $D = 1$ 的情况，按要求输出找到的起始座位编号，若找不到符合要求的编号，输出 $0$ 。 $D = 2$ 的情况只需在系统标记座位空闲，无需输出。

样例

• 输入示例1

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

• 输出示例1

1
6
0
3

• 解释：共有10个座位，5条指令。第1条指令，查找5个连续空位置，此时从1号位置开始的5个位置空闲，因此输出1，并标记它们被使用。第2条指令，查找2个连续空位置，此时从6号位置开始的2个位置空闲，因此输出6，并标记它们被使用。第3条指令，查找5个连续空闲位置，此时没有5个连续空闲位置，因此输出0。第4条指令，从位置3开始，有5个位置的玩家完成体验离开，标记这5个位置空出。第5条指令，查找5个连续空位置，此时从3号位置开始的5个位置空闲，因此输出3，并标记它们被使用。
• 输入示例2

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

• 输出示例2

1
0
5
0
9
11
13
3

• 输入示例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

• 输出示例3

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