Problem text

Обработка видео

Time limit:

7 sec.

Memory limit:

1048576 KByte

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

Всего имеется N видеокарт, каждая из которых обрабатывает кадр за T мс. Одновременно одна видеокарта не может обрабатывать больше одного кадра. Если все видеокарты заняты, то кадр в начале очереди ждёт, пока одна из карт не освободится.

Результаты обработки кадров со всех видеокарт помещаются во вторую общую очередь, которая обрабатывается отдельным процессом по следующему принципу. Пока очередь пуста, процесс ждёт появления первого результата. Как только результат появляется, процесс тут же начинает передавать его клиенту. Время передачи составляет V мс. Соответственно, через V мс после начала передачи процесс будет готов передавать следующий результат.

Для каждого кадра необходимо вычислить момент времени, когда результат по его обработке появится у клиента. Можно считать, что операции добавления и извлечения из очередей происходят мгновенно.

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

В первой строке записаны 4 числа через пробел:

F (1 ≤ F ≤ 10⁵) – количество кадров для обработки.
N (1 ≤ N ≤ 10) – количество видеокарт.
T (1 ≤ T ≤ 100) – время обработки кадра на видеокарте.
V (1 ≤ V ≤ 100) – время на передачу результатов обработки клиенту.

В следующих F строках записано по одному числу X (1 ≤ X ≤ 10⁹) – времена появления кадров. Все времена различны и даны в порядке возрастания.

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

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

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

После вывода каждого ответа программа должна выполнить операцию flush (см. примечание ниже).

Примеры

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

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

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

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

Примечание

Операция flush (сброс данных из буфера в поток) для разных языков выполняется следующим образом:

c++ с библиотекой iostream: std::cout « std::flush; либо std::cout « std::endl; (во втором варианте – также перевод строки)
c++ с библиотекой stdio.h: fflush(stdout);
pascal: flush(output);
java: PrintWriter out = new PrintWriter(System.out); ... out.flush();
C#, Visual Basic: Console.Out.Flush()
Python: import sys ... sys.stdout.flush()

Практикум по программированию

Обработка видео