Miraculous Drug

Interview

Time limit1sMemory limit256 MB

Summary

Each hour uses the cheapest enzyme bought within the last h hours, breaking ties toward the latest hour, and reports purchase counts over a given interval.

Level: Medium4 of 10
Topics: Sliding window, Queue
Solved: No attempts yet

Problem

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.

Input

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$

Output

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.

Examples8

Example 1

Input

6	3	1	6
5	4	4	3	5	6
3	3	2	3
9000	9000	9000

Expected output

1	1	1	3	0	0
1	1

Example 2
Input
```
1 1 1 1
7
```
Expected output
```
1
```
Example 3
Input
```
5 10 1 5
3 1 1 2 5
```
Expected output
```
1	1	3	0	0
```
Example 4
Input
```
6 1 1 6
1 2 3 4 5 6
```
Expected output
```
1	1	1	1	1	1
```
Example 5
Input
```
6 6 1 6
9 8 7 6 5 4
```
Expected output
```
1	1	1	1	1	1
```
Example 6
Input
```
5 5 1 5
4 4 4 4 4
```
Expected output
```
1	1	1	1	1
```
Example 7
Input
```
8 4 3 6
7 0 9 9 0 3 3 1
```
Expected output
```
0	0	4	0
```

Example 8

Input

Expected output

1	1	1	1
2	0	2
1	1