TNVFC1M - Miraculous

no tags 

Joe is an enthusiast biomedical researcher. He is very close to discover the cure for a terrible disease. In order to prepare the miraculous drug he needs to buy a special enzyme, that is quite expensive and unfortunately loses its properties after a fixed period of time. Now Joe is in the clinical trial phase. He needs a drug available at each hour. Thus he has to prepare exactly the same quantity of drug every hour. The price of the enzyme might vary from hour to hour. The cost of the enzyme on hour i is c i . The life time of the enzyme is h hours. Given the prices for the next n hours, Joe has to find out the optimal cost to purchase enzymes such that the drug is available in each of the n hours. If the price is the same Joe prefers to buy fresh enzymes, not to stock them. We assume an unlimited quantity of enzymes is available each hour. Can you help Joe?

Input

The program input is from a text file. The file contains several data sets. A data set starts with the number n (n<10000) of hours. Follows h (h<10000) the number of hours of the enzyme life time, b the starting point, e the ending point of the printing interval (1≤b,e≤n), and the enzyme costs c i (c i <10000), i=1..n. The program prints for each hour in the interval [b,e] the number of enzymes Joe decides to buy. White spaces can occur freely in the input. The input data are correct and terminate with an end of file. 

Output

For each set of data the program prints the result to the standard output from the beginning of a line.

An input/output sample is in the table below. There are two data sets. For the first one n=6, h=3, b=1, e=6, and the costs are 5 4 4 3 5 6 . The result consists of the numbers of enzymes bought every hour, printed from the beginning of the line, separated with tabs.

Example

Input:
6 3 1 6
5 4 4 3 5 6
3 3 2 3
9000 9000 9000

Output:
1 1 1 3 0 0
1 1

hide comments
hf2002: 2023-10-08 00:20:52

i can't understand anything

saurabhshinde: 2021-06-06 08:10:31

poor wording

th3rd_br0: 2020-12-28 12:26:57

what does '0' even mean in verdict ? tag shows solved though !
EDIT : 0 means wa!

Last edit: 2020-12-28 12:43:02
vin__ar: 2020-04-22 20:14:58

calculate ans for [0,n] and print only for [b,e]

zakir068: 2020-04-22 07:15:16

calculating for range b,e cost me 3 wa. b,e is just printing interval.

shammya: 2020-03-28 16:27:15

for those who spent hours and could not make that out ....
1. iterate over the prices
2. for each index find out the minimum of the range [i+h-1,i] and increase the count of the minimum index
3. print the count array from b to e
i used sparse table for finding range minimum.

namhong2001: 2019-10-19 16:14:34

After very long struggling time, i got score. So now I could say 0 means "WA".

ankkt16: 2019-06-19 09:16:32

same here

Last edit: 2019-06-19 09:40:22
elastic99: 2019-05-07 13:11:22

same as akashkandpal0, submission gives 0, any help?

akashkandpal0: 2018-12-18 08:22:53

My submission is getting 0 as result what does it mean? Is it accepted or not ?


Added by:BIDV
Date:2017-09-22
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All