B. 电梯

内存限制:512 MiB 时间限制:800 ms 标准输入输出
题目类型:传统 评测方式:Special Judge

题目描述

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

某公司有一座大厦,大厦有 m 层,自底向上依次称作 1\ldots m 楼(层)。

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

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

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

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

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

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

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

输入格式

第一行: n,m
接下来 m 行,每行两个整数,表示 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 \tt []    
1  
2 \tt []↑3   \tt ☺\:\:1 \tt ☺\:\:2
3 \tt []↑3
4   \tt []←☺\:\:1
5 \tt [☺\:\:1]←☺\:\:3 \tt ☺\:\:4
6 \tt [☺\:\:1→,☺\:\:3→]↑4
7 \tt []↑4
8   \tt []↑4 ☺\:\:4
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
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