587. Ограничитель частоты

Роман $-$ обычный пользователь интернета. Как и многие другие обычные пользователи, Роман очень нетерпелив. Например, сейчас Роман ждёт обновления новостей на главной странице Яндекса и постоянно жмёт Обновить в браузере. Для того, чтобы не перегрузить Яндекс огромным количеством запросов (Роман очень нетерпелив!), все запросы Романа складываются в очередь, откуда отправляются на сервис новостей таким образом, чтобы запросы шли не чаще, чем некоторая заданная в конфигурации частота.

Ограничение на частоту может быть задано двумя способами:

• не более $X$ запросов в секунду
• $1$ запрос не чаще, чем в $Y$ секунд

Каждый запрос Романа будет обработан в тот момент времени, в который его обработка не приведёт к нарушению ограничения на частоту, но, естественно, не раньше того момента, как запрос был отправлен. Для более подробного пояснения смотрите примеры.

Сможете ли вы написать программу, которая моделирует работу сервиса по ограничению частоты запросов и сообщает, в какой момент обработан каждый запрос?

В первой строке записано ограничение частоты в формате X / Y, где $X$ и $Y$ $-$ два целых числа ($1 \le X, Y \le 10^4$), хотя бы одно из которых равно $1$. Если $Y = 1$, то сервис не должен обрабатывать более $X$ запросов в секунду. Если $X = 1$, то сервис не должен обрабатывать более, чем один запрос в $Y$ секунд.

Во второй строке содержится число $N$ ($1 \le N \le 10^5$) $-$ количество запросов обновления страницы, которые Роман отослал на сервер, нажимая кнопку Обновить в браузере.

Следующая строка содержит $N$ целых чисел $t_i$ ($1 \le t_i \le 10^{18}$), разделённых пробелами $-$ времена отсылки запросов, заданные в наносекундах (в одной секунде $10^9$ наносекунд). Гарантируется, что числа $t_i$ расположены по неубыванию.

Выведите $N$ чисел, разделённых пробелами $-$ время обработки каждого запроса. Смотрите примеры для пояснения.

В первом тесте Роман отправляет три запроса. Первый запрос будет обработан сразу же, второй $-$ спустя $10^9$ наносекунд после первого, а третий $-$ спустя $10^9$ наносекунд после второго, поскольку указано ограничение не более, чем 1 запрос в секунду.

Во втором тесте указано ограничение не более 5 запросов в секунду, что позволяет обработать первые пять запросов в момент их поступления. Следующие 4 запроса обработаются спустя $10^9$ наносекунд после соответствующих первых четырёх. Наконец, перед последним запросом Роман, похоже, куда-то отошёл от ноутбука, поэтому запрос будет обработан тогда же, когда и послан, так как это произошло значительно позже остальных запросов.

В третьем тесте частота запросов ограничена не более, чем 1 запрос в 19 секунд, в связи с чем запросы будут обработаны с интервалом в $19 \cdot 10^9$ наносекунд, начиная с момента поступления первого запроса.