Description

NOI2130 is about to take place. To enhance the viewing experience, CCF has decided to evaluate each contestant's score one by one and broadcast the real-time award cutoff score. The award rate for this competition is w%, meaning the lowest score among the top w% of contestants at any given moment is 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 there are contestants with tied scores, all contestants with the same score will receive awards, so the actual number of awardees may exceed the planned number.

As a technical member of the judging panel, your task is to help CCF write a live broadcast program.

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 evaluated. 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 participant's score, the planned number of awardees is 5. However, due to ties, the actual number of awardees becomes 6.

【Data Range】

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

When calculating the planned number of awardees, if floating-point variables (e.g., float or double in C/C++) are used to store the award percentage w%, the result of calculating 5 × 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 compute the accurate value.

Source

CSP2020-J2