题目描述

游乐城的3D游戏体验区广受大家的喜爱，经常爆满。

游戏体验区有 $N$ 个座位（编号 $1 \sim N$）。排队的人群中，有些玩家是一起的，要一起体验，因此他们需要连续的挨在一起的空座位。由于每个玩家选择体验的游戏可能不同，需要体验的时间就可能不同，因此每个玩家完成体验，离开座位的时间并不一定相同。

当有玩家来体验时，告诉管理员，需要 $x$ 个座位。管理员会从 $1 \sim N$ 个座位中，找到连续的 $x$ 个空座位，提供给这 $x$ 个一起来的玩家，并告知这些玩家这 $x$ 个座位中，起始座位的编号（$x$ 个连续座位的第 $1$ 个位置的编号）。然后在系统中登记这 $x$ 个座位被使用。如果找不到连续的 $x$ 个空座位，这批玩家会先去玩其他项目，待会儿再来体验。

如果有多段连续的 $x$ 个空座位，管理员会选择起始座位编号最小的位置，作为第 $1$ 个位置。

每当有玩家完成体验，离开座位时。管理员会登记这些离开的玩家原先使用的一段连续的座位编号（从编号 $p$ 开始的连续个 $x$ 个位置）处于空闲状态。

请你编程，设计一个这样的系统。

输入格式

第 $1$ 行输入两个整数 $N, M$。表示共有 $N$ 个座位，管理员在系统执行了 $M$ 次指令。

接下来的 $M$ 行，每行读入一个指令。

对于每个指令，都需要先读入一个整数 $D$。

如果 $D$ 为 $1$ 表示有玩家要来体验，再输入一个整数 $x$，表示一起来的玩家的数量。此时，系统需要按题意找到连续的 $x$ 个空座位的起始位置的编号。

如果 $D$ 为 $2$ 表示有玩家离开，再输入两个整数 $p, x$，表示从编号 $p$ 开始的连续个 $x$ 的位置（即：$[p, p + x - 1]$）空出。

输出格式

输出若干行，表示针对每一个 $D = 1$ 的情况，按题意输出的起始位置的编号。如果找不到符合题意的起始位置的编号，请输出 $0$。

本题在每一个 $D = 2$ 的情况下，只需要标记好这些位置空出，不需要有输出。有可能准备标记空出的座位中，有些座位本来就是空出的，但这并不影响标记指令的执行。

样例

输入

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

输出

1
6
0
3

数据范围

对于 $10\%$ 的数据，满足 $1 \le N \le 1000$，$1 \le M \le 2000$。

对于另外 $10\%$ 的数据，满足 $1 \le N \le 10000$，$1 \le M \le 2000$。

对于 $100\%$ 的数据，满足 $1 \le N \le 50000$，$1 \le M \le 50000$。