Bus

题意翻译

### 题目描述 有 $n$ 个学生需要去乘坐公交车，第 $i$ 个学生将在 $t_i$ 时间出现在公交车站。我们把马路看成坐标轴 $Ox$，初始时 $x=0$，公交车沿着坐标轴正方向行驶然后返回。第 $i$ 个学生需要到达坐标 $x_i$（$x_i>0$）的点。 公交车按照以下方式移动：最开始它在 坐标轴 $0$ 的位置，学生们不断地上车。公交车的座位容量等于 $m$，当座位坐满时或者当最后一个学生上车后，开始正方向移动。公共汽车速度每分钟一个单位距离。 每次有学生到达下车的地点时，它就会停下来，学生下车需要 $1+\left\lfloor\dfrac{k}{2}\right\rfloor$ 个单位的时间，其中 $k$ 是此时离开的学生人数。当学生都下车后公交车就会掉头回到 $x=0$ 点，中间不会停下来。 请输出每个学生下车的时间。 ### 输入描述 第一行包含两个整数 $n,m$（$n,m \le 10^5$）表示学生人数和公交车座位容量。 接下来的 $n$ 行，每行包含两个整数 $t_i,x_i$（$1 \le t_i \le 10^5, 1 \le x_i \le 10^4$），表示每个学生到达公交站时间和下车地点。这些行是按照 $t_i$ 严格递增的顺序给出的。$x_i$ 的值可以重合。 ### 输出描述 输出 $n$ 个数字，$w_1, w_2, \ldots, w_n, w_i$，表示第 $i$ 个学生下车的时刻。

题目描述

There is a bus stop near the university. The lessons are over, and $ n $ students come to the stop. The $ i $ -th student will appear at the bus stop at time $ t_{i} $ (all $ t_{i} $ 's are distinct). We shall assume that the stop is located on the coordinate axis $ Ox $ , at point $ x=0 $ , and the bus goes along the ray $ Ox $ , that is, towards the positive direction of the coordinate axis, and back. The $ i $ -th student needs to get to the point with coordinate $ x_{i} $ ( $ x_{i}>0 $ ). The bus moves by the following algorithm. Initially it is at point 0. The students consistently come to the stop and get on it. The bus has a seating capacity which is equal to $ m $ passengers. At the moment when $ m $ students get on the bus, it starts moving in the positive direction of the coordinate axis. Also it starts moving when the last ( $ n $ -th) student gets on the bus. The bus is moving at a speed of 1 unit of distance per 1 unit of time, i.e. it covers distance $ y $ in time $ y $ . Every time the bus passes the point at which at least one student needs to get off, it stops and these students get off the bus. The students need $ 1+[k/2] $ units of time to get off the bus, where $ k $ is the number of students who leave at this point. Expression $ [k/2] $ denotes rounded down $ k/2 $ . As soon as the last student leaves the bus, the bus turns around and goes back to the point $ x=0 $ . It doesn't make any stops until it reaches the point. At the given point the bus fills with students once more, and everything is repeated. If students come to the stop when there's no bus, they form a line (queue) and get on the bus in the order in which they came. Any number of students get on the bus in negligible time, you should assume that it doesn't take any time. Any other actions also take no time. The bus has no other passengers apart from the students. Write a program that will determine for each student the time when he got off the bus. The moment a student got off the bus is the moment the bus stopped at the student's destination stop (despite the fact that the group of students need some time to get off).

输入输出格式

输入格式

The first line contains two space-separated integers $ n,m $ ( $ 1<=n,m<=10^{5} $ ) — the number of students and the number of passengers the bus can transport, correspondingly. Next $ n $ lines contain descriptions of the students, one per line. Each line contains a pair of integers $ t_{i},x_{i} $ ( $ 1<=t_{i}<=10^{5},1<=x_{i}<=10^{4} $ ). The lines are given in the order of strict increasing of $ t_{i} $ . Values of $ x_{i} $ can coincide.

输出格式

Print $ n $ numbers $ w_{1},w_{2},...,w_{n} $ , $ w_{i} $ — the moment of time when the $ i $ -th student got off the bus. Print the numbers on one line and separate them with single spaces.

输入输出样例

输入样例 #1

1 10
3 5

输出样例 #1

8

输入样例 #2

2 1
3 5
4 5

输出样例 #2

8 19

输入样例 #3

5 4
3 5
4 5
5 5
6 5
7 1

输出样例 #3

11 11 11 11 20

输入样例 #4

20 4
28 13
31 13
35 6
36 4
52 6
53 4
83 2
84 4
87 1
93 6
108 4
113 6
116 1
125 2
130 2
136 13
162 2
166 4
184 1
192 2

输出样例 #4

51 51 43 40 93 89 86 89 114 121 118 121 137 139 139 152 195 199 193 195

说明

In the first sample the bus waits for the first student for $ 3 $ units of time and drives him to his destination in additional $ 5 $ units of time. So the student leaves the bus at the moment of time $ 3+5=8 $ . In the second sample the capacity of the bus equals $ 1 $ , that's why it will drive the first student alone. This student is the same as the student from the first sample. So the bus arrives to his destination at the moment of time $ 8 $ , spends $ 1+[1/2]=1 $ units of time on getting him off, and returns back to $ 0 $ in additional $ 5 $ units of time. That is, the bus returns to the bus stop at the moment of time $ 14 $ . By this moment the second student has already came to the bus stop. So he immediately gets in the bus, and is driven to his destination in additional $ 5 $ units of time. He gets there at the moment $ 14+5=19 $ . In the third sample the bus waits for the fourth student for $ 6 $ units of time, then drives for $ 5 $ units of time, then gets the passengers off for $ 1+[4/2]=3 $ units of time, then returns for $ 5 $ units of time, and then drives the fifth student for $ 1 $ unit of time.