e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.

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

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

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

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

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

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

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

Ліміт часу 1 секунд
Ліміт використання пам'яті 122.49 MiB
Вхідні дані #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

Пояснення: Для вывода символа табуляции используйте write(chr(9)) в Pascal (Delphi) и "\t" в C++

Джерело 2012 Southeastern Europe Regional Contest, Бухарест, Вінниця, Жовтень 13, Задача G