CF219E.Parking Lot

A parking lot in the City consists of n parking spaces, standing in a line. The parking spaces are numbered from 1 to n from left to right.

When a car arrives at the lot, the operator determines an empty parking space for it. For the safety's sake the chosen place should be located as far from the already occupied places as possible. That is, the closest occupied parking space must be as far away as possible. If there are several such places, then the operator chooses the place with the minimum index from them. If all parking lot places are empty, then the car gets place number 1.

We consider the distance between the i-th and the j-th parking spaces equal to 4·|i - j| meters.

You are given the parking lot records of arriving and departing cars in the chronological order. For each record of an arriving car print the number of the parking lot that was given to this car.

城市中有一个停车场，包含 n 个停车位，呈一条直线排列。停车位从左到右依次编号为 1 到 n。

当一辆汽车到达停车场时，管理员需为其分配一个空闲的停车位。出于安全考虑，所选位置应尽可能远离所有已被占用的停车位，即：该位置到最近的已被占用停车位的距离应尽可能大。若存在多个满足条件的位置，则管理员从中选择编号最小的一个。若所有停车位均为空，则汽车停放在 1 号位。

我们定义第 i 个与第 j 个停车位之间的距离为 $4 \cdot |i - j|$ 米。

现按时间顺序给出一系列汽车到达与离开的记录。对每条汽车到达记录，请输出分配给该车的停车位编号。

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 2·105) — the number of parking places and the number of records correspondingly.

Next m lines contain the descriptions of the records, one per line. The i-th line contains numbers t__i, id__i (1 ≤ t__i ≤ 2; 1 ≤ id__i ≤ 106). If t__i equals 1, then the corresponding record says that the car number id__i arrived at the parking lot. If t__i equals 2, then the corresponding record says that the car number id__i departed from the parking lot.

Records about arriving to the parking lot and departing from the parking lot are given chronologically. All events occurred consecutively, no two events occurred simultaneously.

It is guaranteed that all entries are correct:

• each car arrived at the parking lot at most once and departed from the parking lot at most once,
• there is no record of a departing car if it didn't arrive at the parking lot earlier,
• there are no more than n cars on the parking lot at any moment.

You can consider the cars arbitrarily numbered from 1 to 106, all numbers are distinct. Initially all places in the parking lot are empty.

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^5$），分别表示停车场的车位数量和记录条数。

接下来的 $m$ 行每行描述一条记录。第 $i$ 行包含两个数 $t_i$、$id_i$（$1 \leq t_i \leq 2$；$1 \leq id_i \leq 10^6$）。若 $t_i = 1$，则该记录表示编号为 $id_i$ 的汽车到达了停车场；若 $t_i = 2$，则该记录表示编号为 $id_i$ 的汽车离开了停车场。

关于汽车到达与离开停车场的记录按时间顺序给出。所有事件依次发生，不存在任何两个事件同时发生的情况。

保证所有输入均合法：

• 每辆汽车至多到达停车场一次，且至多离开停车场一次；
• 若某辆汽车有离开记录，则它此前必定已有到达记录；
• 在任意时刻，停车场内的汽车数量均不超过 $n$ 辆。

可将汽车编号视为从 $1$ 到 $10^6$ 的任意整数，且所有编号互不相同。初始时，停车场内所有车位均为空。

For each entry of an arriving car print the number of its parking space. Print the numbers of the spaces in the order, in which the cars arrive to the parking lot.

对于每辆到达的汽车，输出其停车位的编号。按照汽车到达停车场的顺序输出各停车位的编号。