城市中的一个停车场由 n 个停车位组成,排成一排。停车位从左到右编号为1至n。
当汽车到达停车场时,操作员为其确定一个空停车位。为了安全起见,所选地点应尽可能远离已占用的地点。也就是说,最近的占用停车位必须尽可能远。如果有多个这样的位置,则操作员从中选择索引最小的位置。如果所有停车场位都是空的,则汽车获得位置号 1。
我们认为第 i 个和第 j 个停车位之间的距离等于 4·|i - j|米。
您将按时间顺序获得到达和离开车辆的停车场记录。对于到达汽车的每条记录,打印分配给该汽车的停车场号码。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 2·105) — 对应的停车位数量和记录数量。
接下来的 m 行包含记录的描述,每行一个。第 i 行包含数字 ti、idi (1 ≤ ti ≤ 2; 1 ≤ idi ≤ 106)。如果ti等于1,则对应的记录表示id号车到达停车场。如果ti等于2,则对应的记录表示id号车从停车场出发。
按时间顺序给出到达停车场和离开停车场的记录。所有事件连续发生,没有两个事件同时发生。
保证所有条目都是正确的:
- 每辆车最多到达停车场一次,最多离开停车场一次,
- 如果车辆没有提前到达停车场,则没有出发记录,
- 任何时刻停车场上的汽车数量不超过 n 辆。
你可以考虑从1到106任意编号的汽车,所有编号都是不同的。最初停车场的所有位置都是空的。
输出
对于到达的汽车的每个条目,打印其停车位的号码。打印出汽车到达停车场的顺序中的车位编号。
示例
输入 #1
7 11 1 15 1 123123 1 3 1 5 2 123123 2 15 1 21 2 3 1 6 1 7 1 8
输出 #1
1 7 4 2 7 4 1 3