P11178 [ROIR 2018] 电梯 (Day1)

**译自 ROI 2018 Regional. Day1 T3.** ***[Лифт](http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-regional-2018-day1.pdf)*** 某公司有一座大厦，大厦有 $m$ 层，自底向上依次称作 $1\ldots m$ 楼（层）。 有 $n$ 名雇员在大厦中工作，其编号分别为 $1\ldots n$。每天下班时，所有雇员都需坐电梯下到一楼，并离开大厦。已知开始时 $i$ 号雇员位于 $a_i$ 层，该雇员在第 $t_i$ 秒到达该层的电梯口。 每层都有可能有人在等电梯。当一名雇员到达电梯口时，如果这层已经有人摁电梯了，他会等电梯；如果这层没人摁电梯，则他会去摁电梯。摁电梯会给电梯主控发送一个请求信号。 开始时电梯空闲，位于一楼。电梯每秒可以上升 / 下降一层。当第一次有人摁电梯时，电梯会响应该信号，到达对应楼层。如果电梯同时接受到多个信号，则它会响应编号较小的员工的请求信号。 电梯上升至对应楼层时，所有在这层楼等电梯的人都会进入电梯，然后电梯以同样的速度下降，直到电梯到达一楼。对于电梯下降过程中会经过的楼层，如果电梯到达该楼层时该楼层有请求信号，则电梯会在该楼层停，所有在该楼层等电梯的人都会进入电梯。 如果电梯空闲时有至少一个未响应的信号，则电梯会响应最早者。如果有多个最早者，则响应编号最小者。电梯会持续运作，直到 $n$ 名雇员全部到达一楼。 雇员进出电梯的时间忽略不计。每一秒开始时，人们先摁电梯，然后进行对应的行为。（电梯上升 / 下降一层，人们进出电梯，电梯决定响应哪个信号） 请求出每位雇员何时到达一楼。

- 第一行：$n,m$ - 接下来 $n$ 行，每行两个整数，表示 $t_i,a_i$

$n$ 行，每行一个整数，表示答案。

### 样例解释 |时刻|1 楼| 2 楼| 3 楼| 4 楼| |-|-|-|-|-| |0|$\tt []$| || | |1|$\tt []$|| || |2|$\tt []↑3$| |$\tt ☺\:\:1$|$\tt ☺\:\:2$| |3||$\tt []↑3$|$\tt ☺\:\:1$|$\tt ☺\:\:2$| |4| ||$\tt []←☺\:\:1$|$\tt ☺\:\:2$| |5||$\tt [☺\:\:1]←☺\:\:3$|$\tt ☺\:\:4$|$\tt ☺\:\:2$| |6|$\tt [☺\:\:1→,☺\:\:3→]↑4$||$\tt ☺\:\:4$|$\tt ☺\:\:2$| |7||$\tt []↑4$|$\tt ☺\:\:4$|$\tt ☺\:\:2$| |8| ||$\tt []↑4 ☺\:\:4$|$\tt ☺\:\:2$| |9|| |$\tt ☺\:\:4,☺\:\:5$|$\tt []←☺\:\:2$| |10| ||$\tt [☺\:\:2]←☺\:\:4,←☺\:\:5$|| |11||$\tt [☺\:\:2,☺\:\:4,☺\:\:5]$|| | |12|$\tt [☺\:\:2→,☺\:\:4→,☺\:\:5→]$|| || --- |符号|含义|符号|含义| |-|-|-|-| |$\tt []↑3$|电梯将上到 3 楼|$\tt []←☺\:\:1$|1 号雇员进入电梯| |$\tt [☺\:\:1→,☺\:\:3→]$|1 号和 3 号雇员走出电梯|$\tt [☺\:\:1→]↑4$|1 号雇员走出电梯后，电梯准备上到 4 楼| ### 数据范围 对于所有数据，$1 \leqslant n \leqslant 10^5,$ $2 \leqslant m \leqslant 10^9,$ $1 \leqslant t_1 \leqslant t_2 \leqslant \dots \leqslant t_n \leqslant 10^9, 2 \leqslant a_i \leqslant m$. |子任务 #|分值|$n$|$m$|$t_i$| |-|-|-|-|-| |1|15|$n = 1$|$2 \leqslant m \leqslant 100$|$1 \leqslant t_i \leqslant 100$| |2|30|$1 \leqslant n \leqslant 100$|$2 \leqslant m \leqslant 100$|$1 \leqslant t_i \leqslant 100$| |3|16|$1 \leqslant n \leqslant 100$ |$2 \leqslant m \leqslant 10^9$|$1 \leqslant t_i \leqslant 10^9$| |4|12|$1 \leqslant n \leqslant 10^5$|$2 \leqslant m \leqslant 10^4$|$1 \leqslant t_i \leqslant 10^4$| |5|27|$1 \leqslant n \leqslant 10^5$ |$2 \leqslant m \leqslant 10^9$|$1 \leqslant t_i \leqslant 10^9$|