C. Маршрутка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Рядом с университетом находится остановка маршрутки. Пары закончились, и n студентов приходят на остановку. i-ый студент появляется на остановке в момент времени ti (все ti различны).

Будем считать, что остановка находится в точке координатной прямой x = 0, а маршрутка ходит вдоль луча Ox, то есть в сторону положительного направления координатной прямой и обратно. i-ому студенту нужно попасть в точку с координатой xi (xi > 0).

Маршрутка перемещается по следующему алгоритму. Изначально она находится в точке 0. Студенты последовательно приходят на остановку и садятся в нее. Как только в маршрутку сядет m студентов или сядет последний студент из n, она отправится в сторону положительного направления координатной прямой. Маршрутка двигается со скоростью 1 единица расстояния в 1 единицу времени, то есть за время y она проезжает расстояние y.

Каждый раз, когда маршрутка проезжает точку, в которой нужно выйти хотя бы одному студенту, она останавливается, и эти студенты выходят. На высадку студентов тратится 1 + [k / 2] единиц времени, где k — количество студентов, которые выходят в этой точке. Запись [k / 2] обозначает целую часть при делении k на 2. Как только из маршрутки выходит последний студент, она разворачивается и едет без остановок обратно в точку x = 0. Там она вновь наполняется студентами, и история повторяется.

Если студенты приходят на остановку, когда маршрутки там нет, они встают в очередь и садятся в маршрутку в том порядке, в котором они пришли. Посадка любого количества студентов и остальные действия происходит мгновенно, а других пассажиров нет.

Напишите программу, которая определит для каждого студента момент времени, когда он вышел из маршрутки. Моментом выхода студента из маршрутки считайте момент ее остановки в точке выхода студента (несмотря на то, что высадка группы студентов произойдет не мгновенно).

Входные данные

В первой строке записаны через пробел два целых числа n, m (1 ≤ n, m ≤ 105) — количество студентов и количество мест в маршрутке, соответственно. Далее в n строках описаны студенты, по одному в строке. Каждая строка содержит пару целых чисел ti, xi (1 ≤ ti ≤ 105, 1 ≤ xi ≤ 104). Строки заданы в порядке строгого возрастания ti. Значения xi могут совпадать.

Выходные данные

Выведите n чисел w1, w2, ..., wn, wi — момент времени, когда i-ый студент вышел из маршрутки. Числа выводите в одну строку и разделяйте единичными пробелами.

Примеры
Входные данные
1 10
3 5
Выходные данные
8
Входные данные
2 1
3 5
4 5
Выходные данные
8 19
Входные данные
5 4
3 5
4 5
5 5
6 5
7 1
Выходные данные
11 11 11 11 20
Входные данные
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
Выходные данные
51 51 43 40 93 89 86 89 114 121 118 121 137 139 139 152 195 199 193 195
Примечание

В первом примере маршрутка ждет первого студента 3 единицы времени и отвозит его до места назначения за 5 единиц времени. То есть студент выходит из маршрутки в момент времени 3 + 5 = 8.

Во втором примере вместимость маршрутки равна 1, поэтому сначала она повезет одного первого студента. Этот студент — такой же, как студент в первом примере, то есть маршрутка доезжает до его места назначения в момент времени 8, тратит на высадку 1 + [1 / 2] = 1 единицу времени, и возвращается назад еще за 5 единиц времени. Таким образом, маршрутка возвращается назад в момент времени 14. К этому моменту второй студент уже подошел к остановке, поэтому он садится в маршрутку, 5 единиц времени едет до места назначения, и приезжает в момент 14 + 5 = 19.

В третьем примере маршрутка ждет четвертого студента 6 единиц времени, затем едет 5 единиц времени, затем высаживает студентов за 1 + [4 / 2] = 3 единиц времени, возвращается за 5 единиц времени, везет пятого студента 1 единицу времени.