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⁵) — 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⁵, 1 ≤ x_i ≤ 10⁴). The lines are given in the order of strict increasing of t_i. Values of x_i can coincide.

Print n numbers w₁, w₂, ..., 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.