Miraculous Drug

Joe is a biomedical researcher. He is close to a cure for a terrible disease. Making the drug requires a special enzyme that is expensive and loses its properties after a fixed time. The clinical trial phase needs one dose of the drug every hour, and one dose takes one enzyme.

Prices are given for the next $n$ hours. At hour $i$ Joe can buy any number of enzymes at price $c_i$ each. An enzyme lives for $h$ hours, so an enzyme bought at hour $i$ can be used at hours $i$ through $i + h - 1$. Joe uses one enzyme at each of the hours $1$ through $n$. Find the plan with the smallest total cost.

When prices tie, Joe buys the fresher enzyme instead of stocking one early. That fixes a single plan: the enzyme used at hour $i$ is bought at the cheapest hour of the interval $[\max(1,\ i - h + 1),\ i]$, and if several hours are cheapest, at the latest of them.

The input holds several data sets and ends at end of file. Each data set holds the number of hours $n$, the enzyme lifetime $h$, the first hour $b$ and the last hour $e$ of the printing interval, and then the prices $c_1, c_2, \dots, c_n$, in that order. White space and line breaks may appear freely between numbers.

• $1 \le n < 10000$
• $1 \le h < 10000$
• $1 \le b \le e \le n$
• $0 \le c_i < 10000$

For each data set print one line, starting at the beginning of the line, with the number of enzymes Joe buys at each of the hours $b$ through $e$, separated by tab characters.