B. Обработка запросов
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этой задаче от вас требуется промоделировать поведение однопоточного сервера. Серверу поступят n запросов, для каждого из которых дан момент поступления ti и продолжительность обработки di. Известно, что все ti различны.

При поступлении нового запроса сервер может совершить одно из трёх действий:

  1. Если сервер свободен и очередь запросов пуста, то новый запрос сразу начинает выполняться.
  2. Если сервер занят и в очереди находится строго меньше b запросов, ожидающих выполнения, то новый запрос добавляется в конец очереди.
  3. Если сервер занят и в очереди находится ровно b запросов, ожидающих выполнения, то новый запрос отклоняется и выполнен уже не будет.

Как только сервер заканчивает обрабатывать очередной запрос, он переходит к следующему из очереди, если она не пуста. Считайте, что если какой-то запрос пришёл в момент времени x, и в этот же момент времени сервер освободился и очередь не пуста, то сначала начнёт обрабатываться запрос из очереди, а затем произойдет появление нового запроса.

Для каждого запроса найдите момент окончания его обработки или выведите для него -1, если он будет отклонён.

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

В первой строке входных данных содержатся целые числа n и b (1 ≤ n, b ≤ 200 000) — количество запросов и максимальный размер очереди соответственно.

Далее в n строках заданы описания запросов в хронологическом порядке. Каждое описание запроса записано на отдельной строке и состоит из двух целых чисел ti и di (1 ≤ ti, di ≤ 109), где ti — момент поступления i-го запроса, а di — продолжительность его обработки. Значения ti строго возрастают, то есть ti - 1 < ti для всех i > 1.

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

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

Примеры
Входные данные
5 1
2 9
4 8
10 9
15 2
19 1
Выходные данные
11 19 -1 21 22
Входные данные
4 1
2 8
4 8
10 9
15 2
Выходные данные
10 18 27 -1
Примечание

Рассмотрим первый пример.

  1. Первый запрос начнёт обрабатываться сервером в момент времени 2, и сервер закончит его обработку в момент времени 11.
  2. За это время поступит второй запрос (в момент времени 4), но так как сервер будет занят, то этот запрос попадёт в очередь.
  3. В момент времени 10 (сервер все еще будет занят обработкой первого запроса) поступит третий запрос, но так как максимальный размер очереди равен 1 и в очереди уже будет находится второй запрос, то третий запрос будет отклонён.
  4. В момент времени 11 второй запрос будет взят из очереди и начнёт обрабатываться.
  5. В момент времени 15 поступит четвёртый запрос. Поскольку сервер занят, а очередь пуста, то запрос будет добавлен в очередь.
  6. В момент времени 19 происходят одновременно два события: сервер заканчивает обрабатывать второй запрос и поступает пятый запрос. Сначала будет завершена обработка второго запроса, затем запрос четыре будет изъят из очереди и отправлен на обработку, а потом в очередь будет добавлен запрос номер 5.
  7. Сервер закончит обработку четвертого запроса в момент времени 21. Из очереди будет извлечён пятый запрос.
  8. Сервер закончит обработку пятого запроса в момент времени 22.