eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Чудотворное лекарство

Чудотворное лекарство

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Джо - энтузиаст биомедицинских исследований. Он очень близок к открытию лекарства от страшной болезни. Для подготовки чудотворного препарата он должен купить специальный фермент - довольно дорогой и, к сожалению, теряющий свои свойства после определенного периода времени. Сейчас Джо находится в клинической стадии испытания. Препарат ему необходим каждый час. То есть он должен приготавливать каждый час одно и то же количество препарата. Стоимость фермента может варьироваться час от часа. Его стоимость в час i составляет c[i]. Время жизни фермента h часов. Зная цену в следующие n часов, Джо необходимо найти оптимальную цену, за которую он сможет покупать фермент таким образом, чтобы лекарство было доступно в каждый из n часов. В случае одинаковой цены Джо предпочитает покупать более свежий фермент, не запасаясь им. Каждый час для покупки доступно неограниченное количество фермента. Можете ли Вы ему помочь?

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

Состоит из нескольких тестов. Каждый тест начинается количеством часов n (n < 10000). Далее следует время h (h < 10000) жизни фермента, начальная b и конечная e (1b, en) точка интервала исследования, и стоимость фермента c[i] (c[i] < 10000), i = 1 .. n.

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

Для каждого часа из интервала [b, e] вывести количество ферментов, которое Джо необходимо приобрести. Выводимые числа следует разделять символами табуляции.

В примере заданы два теста. Для первого теста n = 6, h = 3, b = 1, e = 6, стоимости соответственно равны 5 4 4 3 5 6. Количество купленных ферментов для каждого часа следует выводить с начала строки, разделяя символами табуляции.

Пример

Входные данные #1
6  3  1  6
5  4  4  3  5  6
3  3  2  3
9000  9000  9000
Выходные данные #1
1	1	1	3	0	0
1	1
Источник 2012 Southeastern Europe Regional Contest, Бухарест, Винница, Октябрь 13, Задача G