#739. CSPJ2020B直播获奖 (Live Awards Ceremony)

CSPJ2020B直播获奖 (Live Awards Ceremony)

Description

NOI2130 will be held soon. In order to improve the viewing experience, CCF decided to reveal the scores of each participant one by one and broadcast real-time cutoffs. The win percentage of the competition is w%w\%, which means that among the participants who are currently in the top w%w\%, the minimum score of a participant is the current cutoff for winning.

More specifically, if the scores of pp participants have been revealed, the number of winners according to current scores is max(1,p×w%)\max(1, \lfloor p \times w\%\rfloor), where ww is the win percentage of the competition, x\lfloor x \rfloor is the largest integer that doesn't exceed xx, and max(x,y)\max(x, y) is the the larger number out of xx and yy. If there are multiple participants with the same score as the cutoff, all of them are also winners, so the actual number of winners may be more than calculated above.

As a technician of the evaluation team, please help CCF write a live broadcast program.

Input Format

The first line contains two integers nn and ww - the total number of participants and the win percentage respectively.

The second line contains nn integers denoting the scores of the participants that are revealed one by one (from left to right).

Output Format

Print a single line containing nn space-separated non-negative integers denoting the cutoffs after the participants' scores are revealed one by one. The ii-th integer should be the cutoff after the scores of the first ii participants have been revealed.

10 60
200 300 400 500 600 600 0 300 200 100
200 300 400 400 400 500 400 400 300 300

The first table below shows the number of winners as calculated by the formula after each participant's score is revealed. The first row contains the number of participants whose scores have been revealed, and the second row contains the corresponding number of winners as calculated by the formula. Note that after the 9th participant's score is revealed, the calculated number of winners is 5, but because there is another participant having the cutoff score, the actual number of winners is 6.

The second table below shows the scores of the participants from high to low (where the underlined score is the cutoff).

10 30
100 100 600 100 100 100 100 100 100 100
100 100 600 600 600 600 100 100 100 100

Constraints

Tests 131 \sim 3: n=10n = 10
Tests 464 \sim 6: n=500n = 500
Tests 7107 \sim 10: n=2000n = 2000
Tests 111711 \sim 17: n=104n = 10^4
Tests 182018 \sim 20: n=105n = 10^5

For all the tests, each participant's score is a non-negative integer not greater than 600600, the win percentage ww is a positive integer, and 1w991 \le w \le 99.

For calculating the number of winners, if you use floating-point numbers (such as float, double in C, C++, real, double, extended in Pascal, etc.) to store the win percentage ww, the result of 5×60%5 \times 60\% may be 3.0000013.000001, or it may be 2.9999992.999999, or something else. The result of rounding down a number like this may be uncertain. Therefore, it is recommended to use only integers to calculate accurate values.