一年一度的园丁大赛开始了。
作为一个合格的园丁，种树和挖树，是必备的基本技能。本届园丁大赛的第 1 个竞技项目就是种树和挖树。
组委会准备了足够数量的树苗用于比赛，每棵树苗都有一个唯一的编号。
比赛在一个长方形的场地上进行，场地被划分为 N 块面积大小相等的空地，编号从 1 到 N，每块空地最多只能种一棵树，所有的空地在一条直线上。初始状态下，所有的空地都没有被种树。
比赛开始，裁判会依次发出 M 条指令，指令共有两种：
指令1. 种树。
将编号为 X_i 的树苗，栽到场地的某块空地上。
如果场地上没有树苗，参赛者需要将树苗种在 1 号空地上。
如果场地上已经有树苗了，则需要将编号为 X_i 的树苗种到距离已有树苗的最小距离最大的空地上，如果有多个位置满足要求，选择编号最小的空地种树苗。
指令2. 挖树。
将编号为 X_i 的树苗，挖走。
请编程输出，对于每个种树指令，园丁需要种树的空地编号。
第一行包含两个正整数 N 和 M，表示场地大小和指令数量。
接下来 M 行，每行有两个整数 Op_i 和 X_i，表示第 i 个指令的类型和需要操作的树苗的编号。
如果 Op_i 的值为 1，表示要在场地上找一个空地种编号为 X_i 的树苗。
如果 Op_i 的值为 2，表示将场地上编号为 X_i 的树苗挖走。
本题数据保证所有操作都是合法的，即：种树时，场地上一定存在空地，挖树时，场地上一定存在对应编号的树苗。
对于每个种树指令，按题目要求输出一个空地编号，输出的空地编号之间用空格隔开。
10 9 1 100 1 200 1 300 1 400 2 300 1 500 2 200 2 400 1 600
1 10 5 3 6 10
7 11 1 15 1 123 1 3 1 5 2 123 2 15 1 21 2 3 1 6 1 7 1 8
1 7 4 2 7 4 1 3
100 20 1 10 1 20 1 30 1 40 1 50 1 60 1 70 1 80 1 90 1 100 2 20 2 30 2 40 2 50 2 90 1 110 1 120 1 130 1 140 1 150
1 100 50 75 25 13 37 62 87 7 100 81 25 49 71
共有 10 块空地，9 个指令。
第 1 个指令为，种编号为 100 的树苗，按题意种在 1 号空地上。
第 2 个指令为，种编号为 200 的树苗，此时 10 号空地离已有的 1 号位置的树苗最远，因此种在 10 号空地上。
第 3 个指令为，种编号为 300 的树苗，此时 5 号空地离 1 号位置的树苗的距离为 4，离 10 号位置的距离为 5，最小距离为 4，分析可知，该空地满足题意要求的距已有树苗的最小距离最大的要求。虽然 6 号空地也满足此要求，但 5 号空地的编号更小，因此种在 5 号空地上。
\dots
对于 30\% 的数据，满足 1 \le n \le 1000 ，1 \le m \le 1000。
对于 60\% 的数据，满足 1 \le n \le 200000，1 \le m \le 2000。
对于 100\% 的数据 满足 1 \le n,m \le 200000，1 \le X_i \le 10^6，Op_i \in [1,2]。