D. Статистика обработки роликов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Социальная сеть для собак ВБудке имеет k специальных серверов для пережатия загружаемых роликов про кошечек. Каждый ролик после загрузки должен быть обработан на одном (любом) из серверов, и только после этого сохранен в соцсети.

Известно, что каждый сервер пережимает минутный фрагмент за одну секунду. Таким образом, на любом из серверов видеофайл длительность m минут пережимается за m секунд.

Известно время загрузки в соцсеть каждого из n роликов (в секундах с момента общего старта серверов). Все ролики поступают в разные моменты времени и обрабатываются в порядке поступления. Если ролик поступил в момент времени s, то его можно начать обрабатывать сразу же в этот момент. Некоторые из роликов могут ожидать обработки из-за занятости всех серверов. В таком случае как только какой-либо сервер освободится, он сразу же начнет обрабатывать очередной ролик. Ожидающие обработки ролики складываются в очередь. Если к моменту начала обработки свободны несколько серверов, то его начинает обрабатывать любой из них.

Для каждого из роликов определите момент окончания его обработки.

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

В первой строке входных данных записаны целые числа n и k (1 ≤ n, k ≤ 5·105) — количество роликов и серверов соответственно.

Далее в n строках следуют описания роликов парами целых чисел si, mi (1 ≤ si, mi ≤ 109), где si — время в секундах, когда пришел i-й ролик, а mi — его длительность в минутах. Гарантируется, что все si различны и ролики заданы в хронологическом порядке загрузки, то есть в порядке увеличения si.

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

Выведите n чисел e1, e2, ..., en, где ei — время в секундах от начала работы серверов, когда i-й ролик будет обработан.

Примеры
Входные данные
3 2
1 5
2 5
3 5
Выходные данные
6
7
11
Входные данные
6 1
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
6 3
Выходные данные
1000000001
2000000001
3000000001
4000000001
5000000001
5000000004