You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

译自 ROI 2018 Regional. Day1 T3. Лифт

某公司有一座大厦，大厦有 $m$ 层，自底向上依次称作 $1\ldots m$ 楼（层）。

有 $n$ 名雇员在大厦中工作，其编号分别为 $1\ldots n$。每天下班时，所有雇员都需坐电梯下到一楼，并离开大厦。已知开始时 $i$ 号雇员位于 $a_i$ 层，该雇员在第 $t_i$ 秒到达该层的电梯口。

每层都有可能有人在等电梯。当一名雇员到达电梯口时，如果这层已经有人摁电梯了，他会等电梯；如果这层没人摁电梯，则他会去摁电梯。摁电梯会给电梯主控发送一个请求信号。

开始时电梯空闲，位于一楼。电梯每秒可以上升 / 下降一层。当第一次有人摁电梯时，电梯会响应该信号，到达对应楼层。如果电梯同时接受到多个信号，则它会响应编号较小的员工的请求信号。

电梯上升至对应楼层时，所有在这层楼等电梯的人都会进入电梯，然后电梯以同样的速度下降，直到电梯到达一楼。对于电梯下降过程中会经过的楼层，如果电梯到达该楼层时该楼层有请求信号，则电梯会在该楼层停，所有在该楼层等电梯的人都会进入电梯。

如果电梯空闲时有至少一个未响应的信号，则电梯会响应最早者。如果有多个最早者，则响应编号最小者。电梯会持续运作，直到 $n$ 名雇员全部到达一楼。

雇员进出电梯的时间忽略不计。每一秒开始时，人们先摁电梯，然后进行对应的行为。（电梯上升 / 下降一层，人们进出电梯，电梯决定响应哪个信号）

请求出每位雇员何时到达一楼。

输入格式

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

输出格式

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

5 4
2 3
2 4
5 2
5 3
9 3

提示

样例解释

数据范围

对于所有数据，$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$.