Социальная сеть для собак ВБудке имеет k специальных серверов для пережатия загружаемых роликов про кошечек. Каждый ролик после загрузки должен быть обработан на одном (любом) из серверов, и только после этого сохранен в соцсети.
Известно, что каждый сервер пережимает минутный фрагмент за одну секунду. Таким образом, на любом из серверов видеофайл длительность m минут пережимается за m секунд.
Известно время загрузки в соцсеть каждого из n роликов (в секундах с момента общего старта серверов). Все ролики поступают в разные моменты времени и обрабатываются в порядке поступления. Если ролик поступил в момент времени s, то его можно начать обрабатывать сразу же в этот момент. Некоторые из роликов могут ожидать обработки из-за занятости всех серверов. В таком случае как только какой-либо сервер освободится, он сразу же начнет обрабатывать очередной ролик. Ожидающие обработки ролики складываются в очередь. Если к моменту начала обработки свободны несколько серверов, то его начинает обрабатывать любой из них.
Для каждого из роликов определите момент окончания его обработки.
Выходные данные
Выведите n чисел e1, e2, ..., en, где ei — время в секундах от начала работы серверов, когда i-й ролик будет обработан.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 5
2 5
3 5
|
6
7
11
|
|
2
|
6 1
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
6 3
|
1000000001
2000000001
3000000001
4000000001
5000000001
5000000004
|