强哥最近得到了一个神奇的魔法帽，这顶帽子里最开始装着一排从小到大的数字 $a$，这些数字从 $1$ 到 $N$ 依次排列。同时，强哥还有一个空的篮子 $b$。强哥可以对这两个容器进行以下三种操作：

1. 移走数字：强哥会从魔法帽中取出最小的数字，并将其放入篮子 $b$。
2. 移出篮子：强哥会从篮子 $b$ 中移走指定的数字 $x$（保证篮子里一定有这个数字）。
3. 查询篮子：强哥想知道篮子 $b$ 中当前的最小数字。

强哥想知道经过 $Q$ 次操作后，他的每次查询结果是什么。

数据范围

• $1 \leq N \leq 5 \times 10^5$
• $2 \leq Q \leq 5 \times 10^5$
• 所有输入值均为整数。

输入格式

输入通过标准输入提供，格式如下：

$N$ $Q$

$event_1$

$event_2$

...

$event_Q$

每个事件 event_i 表示一个操作，有以下三种形式之一：

• 1 表示移走魔法帽中最小的数字并放入篮子 $b$。
• 2 x 表示从篮子 $b$ 中移走数字 $x$（保证 $x$ 一定在篮子里）。
• 3 表示查询篮子 $b$ 中当前的最小值。

输出格式

对于每个查询操作 3，输出篮子 $b$ 中的最小值，每个结果占一行。

示例

输入样例 1

4 10
1
1
3
2 1
1
2 3
3
1
2 2
3

输出样例 1

1
2
4

解释：

• 初始状态：$a = [1, 2, 3, 4]$, $b = []$
• 操作 1：移走 $a$ 中最小的数字 1，$a = [2, 3, 4]$, $b = [1]$
• 操作 1：移走 $a$ 中最小的数字 2，$a = [3, 4]$, $b = [1, 2]$
• 操作 3：查询 $b$ 的最小值，输出 1。
• 操作 2：移走 $b$ 中的数字 1，$b = [2]$
• 操作 1：移走 $a$ 中最小的数字 3，$a = [4]$, $b = [2, 3]$
• 操作 2：移走 $b$ 中的数字 3，$b = [2]$
• 操作 3：查询 $b$ 的最小值，输出 2。
• 操作 1：移走 $a$ 中最小的数字 4，$a = []$, $b = [2, 4]$
• 操作 2：移走 $b$ 中的数字 2，$b = [4]$
• 操作 3：查询 $b$ 的最小值，输出 4。

提示

强哥希望你高效完成任务，因为魔法帽中的数字和操作次数可能非常多！快来帮助强哥管理好他的魔法帽和篮子吧！