题目描述

一年一度的园丁大赛开始了。

作为一个合格的园丁，种树和挖树，是必备的基本技能。本届园丁大赛的第 $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

数据范围

对于 $100\%$ 的数据 满足 $1 \le N, M \le 200000$，$1 \le X_i \le 10^6$，$Op_i \in [1, 2]$。