CF172C.Bus

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).

大学附近有一个公交车站。课程结束，有 $n$ 名学生来到车站。第 $i$ 名学生将在时刻 $t_i$ 到达车站（所有 $t_i$ 互不相同）。

我们假设车站位于坐标轴 $Ox$ 上的点 $x = 0$ 处，而公交车沿射线 $Ox$ 行驶，即先朝坐标轴正方向行驶，再返回。第 $i$ 名学生需要到达坐标为 $x_i$ 的地点（其中 $x_i > 0$）。

公交车按如下算法运行：初始时，公交车停在位置 $0$。学生们依次到达车站并上车。公交车的载客容量为 $m$ 人。当车上已有 $m$ 名学生时，公交车立即启动，向坐标轴正方向行驶；此外，若第 $n$ 名（即最后一名）学生上车时车上尚未满员，公交车也立即启动。公交车的速度为每单位时间行驶 1 单位距离，即行驶距离 $y$ 所需时间为 $y$。

每当公交车经过某个地点，且该地点至少有一名学生需要下车时，公交车将停车，这些学生随即下车。学生下车所需时间为 $1 + \left\lfloor k / 2 \right\rfloor$ 单位时间，其中 $k$ 为在此地点下车的学生人数；$\left\lfloor k / 2 \right\rfloor$ 表示对 $k/2$ 向下取整。当最后一名学生下车后，公交车立即掉头，返回至点 $x = 0$；在返回途中不作任何停靠，直至抵达该点。到达 $x = 0$ 后，公交车再次搭载学生，整个过程重复进行。

若学生到达车站时公交车不在，他们将排队等候（形成队列），并按到达顺序依次上车。任意数量的学生上车均耗时可忽略不计（即视为瞬时完成）。其他所有操作亦不消耗时间。公交车上除学生外无其他乘客。

请编写一个程序，对每名学生，输出其下车时刻。注意：某学生下车的时刻定义为公交车停靠在其目的地站点的时刻（尽管该批学生实际下车需额外耗时）。

The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) — 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 ≤ 105, 1 ≤ x__i ≤ 104). The lines are given in the order of strict increasing of t__i. Values of x__i can coincide.

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别表示学生的数量和公交车一次可运送的乘客数量。接下来的 $n$ 行每行描述一名学生，共 $n$ 行。每行包含一对整数 $t_i$、$x_i$（$1 \leq t_i \leq 10^5$，$1 \leq x_i \leq 10^4$）。这些行按 $t_i$ 的严格递增顺序给出。$x_i$ 的值可以相同。

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.

输出 n 个数字 _w_₁, _w_₂, ..., w__n，其中 w__i 表示第 i 个学生下车的时刻。将这些数字在同一行输出，用单个空格分隔。

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.

在第一个样例中，公交车等待第一名学生 3 个单位时间，再用额外的 5 个单位时间将其送达目的地。因此，该学生在时刻 $3 + 5 = 8$ 下车。

在第二个样例中，公交车的容量为 1，因此它将单独运送第一名学生。该学生与第一个样例中的学生相同。因此，公交车在时刻 8 到达其目的地，花费 $1 + \left\lfloor \frac{1}{2} \right\rfloor = 1$ 个单位时间让学生下车，并再用额外的 5 个单位时间返回至位置 0。即，公交车在时刻 14 返回到公交站。此时，第二名学生已到达公交站，因此他立即上车，并再用额外的 5 个单位时间被送达目的地。他于时刻 $14 + 5 = 19$ 到达。

在第三个样例中，公交车等待第四名学生 6 个单位时间，然后行驶 5 个单位时间，接着花费 $1 + \left\lfloor \frac{4}{2} \right\rfloor = 3$ 个单位时间让学生下车，再用 5 个单位时间返回，最后用 1 个单位时间运送第五名学生。