В этой задаче от вас требуется промоделировать поведение однопоточного сервера. Серверу поступят n запросов, для каждого из которых дан момент поступления ti и продолжительность обработки di. Известно, что все ti различны.
При поступлении нового запроса сервер может совершить одно из трёх действий:
- Если сервер свободен и очередь запросов пуста, то новый запрос сразу начинает выполняться.
- Если сервер занят и в очереди находится строго меньше b запросов, ожидающих выполнения, то новый запрос добавляется в конец очереди.
- Если сервер занят и в очереди находится ровно b запросов, ожидающих выполнения, то новый запрос отклоняется и выполнен уже не будет.
Как только сервер заканчивает обрабатывать очередной запрос, он переходит к следующему из очереди, если она не пуста. Считайте, что если какой-то запрос пришёл в момент времени x, и в этот же момент времени сервер освободился и очередь не пуста, то сначала начнёт обрабатываться запрос из очереди, а затем произойдет появление нового запроса.
Для каждого запроса найдите момент окончания его обработки или выведите для него -1, если он будет отклонён.
Выходные данные
Выведите последовательность n целых чисел e1, e2, ..., en, где ei — момент окончания обработки i-го запроса (нумерация в порядке поступления) или - 1, если i-й запрос будет проигнорирован.
Примечание
Рассмотрим первый пример.
- Первый запрос начнёт обрабатываться сервером в момент времени 2, и сервер закончит его обработку в момент времени 11.
- За это время поступит второй запрос (в момент времени 4), но так как сервер будет занят, то этот запрос попадёт в очередь.
- В момент времени 10 (сервер все еще будет занят обработкой первого запроса) поступит третий запрос, но так как максимальный размер очереди равен 1 и в очереди уже будет находится второй запрос, то третий запрос будет отклонён.
- В момент времени 11 второй запрос будет взят из очереди и начнёт обрабатываться.
- В момент времени 15 поступит четвёртый запрос. Поскольку сервер занят, а очередь пуста, то запрос будет добавлен в очередь.
- В момент времени 19 происходят одновременно два события: сервер заканчивает обрабатывать второй запрос и поступает пятый запрос. Сначала будет завершена обработка второго запроса, затем запрос четыре будет изъят из очереди и отправлен на обработку, а потом в очередь будет добавлен запрос номер 5.
- Сервер закончит обработку четвертого запроса в момент времени 21. Из очереди будет извлечён пятый запрос.
- Сервер закончит обработку пятого запроса в момент времени 22.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1
2 9
4 8
10 9
15 2
19 1
|
11 19 -1 21 22
|
|
2
|
4 1
2 8
4 8
10 9
15 2
|
10 18 27 -1
|