Description

NOI2130 is about to take place. To enhance the viewing experience, CCF has decided to evaluate and announce each contestant's score one by one, broadcasting the real-time award cutoff score. The award rate for this competition is w%, meaning the lowest score among the top w% of contestants based on the current rankings will serve as the real-time cutoff score.

More specifically, if the scores of p contestants have been evaluated so far, the planned number of awardees is max(1, ⌊p × w%⌋), where w is the award percentage, ⌊x⌋ denotes the floor of x, and max(x, y) represents the larger of x and y. If multiple contestants have the same score, all contestants tied at that score will receive awards, so the actual number of awardees may exceed the planned number.

As a technical member of the judging panel, you are tasked with writing a live broadcast program for CCF.

Input Format

The first line contains two positive integers, n and w, representing the total number of contestants and the award percentage, respectively.

The second line contains n non-negative integers, representing the scores of the contestants as they are evaluated one by one.

Output Format

A single line containing n non-negative integers, representing the real-time award cutoff scores after each contestant's score is announced. Separate adjacent integers with a single space.

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

200 300 400 400 400 500 400 400 300 300

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

100 100 600 600 600 600 100 100 100 100

Hint

Sample 1 Explanation

Note: After evaluating the 9th contestant's score, the planned number of winners is 5. However, due to ties, the actual number of winners becomes 6.

Data Range

For all test cases, each contestant's score is a non-negative integer not exceeding 600, and the award percentage ( w ) is a positive integer where ( 1 \leq w \leq 99 ).

When calculating the planned number of winners, if floating-point variables (such as float or double in C/C++) are used to store the award percentage ( w% ), the result of ( 5 \times 60% ) might be 3.000001 or 2.999999, leading to uncertainty in the floor value. Therefore, it is recommended to use only integer variables to ensure accurate calculations.

Source

CSP2020-J2