题目描述

译自 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

输出

6
12
6
12
12

---

时刻表

时刻	1 楼	2 楼	3 楼	4 楼
0	[]
1
2	[]↑3		☺1	☺2
3		[]↑3
4			[]←☺1
5	[☺1]←☺3		☺4
6	[☺1→,☺3→]↑4
7		[]↑4
8			[]↑4 ☺4
9		☺4,☺5	[]←☺2
10			[☺2]←☺4,←☺5
11		[☺2,☺4,☺5]
12	[☺2→,☺4→,☺5→]

---

符号含义

符号	含义
[]↑3	电梯将上到 $3$ 楼
[]←☺1	$1$ 号雇员进入电梯
[☺1→,☺3→]	$1$ 号和 $3$ 号雇员走出电梯
[☺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$
3	16		$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		$2 \leqslant m \leqslant 10^9$	$1 \leqslant t_i \leqslant 10^9$