Чудодійний засіб
Джо — ентузіаст біомедичних досліджень, який майже винайшов ліки від серйозної хвороби. Для приготування цього чудодійного препарату йому потрібен спеціальний фермент, який є досить дорогим і втрачає свої властивості через певний час. Зараз Джо перебуває на клінічній стадії випробувань, і йому необхідно мати препарат кожну годину. Це означає, що він повинен щогодини готувати однакову кількість препарату. Вартість ферменту може змінюватися щогодини, і його ціна в годину i дорівнює c[i]. Термін дії ферменту становить h годин. Знаючи ціни на наступні n годин, Джо потрібно знайти оптимальну стратегію покупки ферменту, щоб ліки були доступні в кожну з n годин. Якщо ціни однакові, Джо віддає перевагу купувати свіжіший фермент, не накопичуючи його. Щогодини доступна необмежена кількість ферменту. Чи можете ви допомогти йому?
Вхідні дані
Складаються з кількох тестів. Кожен тест починається з кількості годин n (n < 10000). Далі йде термін дії ферменту h (h < 10000), початкова b та кінцева e (1 ≤ b, e ≤ n) точка інтервалу дослідження, і вартість ферменту c[i] (c[i] < 10000), i = 1 .. n.
Вихідні дані
Для кожної години з інтервалу [b, e] виведіть кількість ферментів, які Джо повинен придбати. Виведені числа слід розділяти символами табуляції.
У прикладі наведено два тести. Для першого тесту n = 6, h = 3, b = 1, e = 6, а вартості відповідно рівні 5 4 4 3 5 6. Кількість куплених ферментів для кожної години слід виводити з початку рядка, розділяючи символами табуляції.