题目描述

一块场地被划分为一排 $N$ 块空地，编号为 $1$ 到 $N$。每块空地最多种一棵树，初始时场地上没有树。每棵树苗都有唯一编号。

接下来有 $M$ 条操作：

• 1 X：种下编号为 $X$ 的树苗。如果场地上没有树，将它种在 $1$ 号空地；否则选择一块空地，使它到场地上距离最近的树的距离尽量大。如果有多块空地满足条件，选择编号最小的空地。
• 2 X：挖走编号为 $X$ 的树苗。

两块空地之间的距离为它们编号之差的绝对值。

对于每个种树操作，请输出树苗被种在哪一块空地。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含两个整数 $Op_i,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

数据范围与提示

• $1 \le N,M \le 2\times10^5$
• $1 \le X_i \le 10^6$
• $Op_i$ 为 $1$ 或 $2$