Robin Hood

Interview

Time limit3sMemory limit256 MB

Summary

Given N wealths, repeatedly take 100 from the richest person (first on ties) K times and print the final wealth, or impossible if a theft would leave someone at 0 or less.

Level: Easy3 of 10
Topics: Heap, Simulation
Solved: No attempts yet

Problem

Elders of the village foresee a harsh winter, and Robin Hood is worried about the wellbeing of those less well off. As usual, he plans to redistribute some wealth in the kingdom by stealing from the rich. He estimates that $K$ heists will be required.

Robin Hood follows a moral codex that determines his target. He always steals from the richest person. If several people are tied for the most wealth, he picks the first one on the list. He steals 100 monetary units at a time and never steals from anybody who would be left with $0$ (or less) money after the heist.

Given the wealth of $N$ men and the number of heists $K$ , compute the amount of wealth left after $K$ heists, following the moral codex.

Input

The first line contains two space-separated integers $N$ and $K$ . The second line contains $N$ space-separated integers $P_i$ , the wealth of each of Robin Hood's targets.

Output

Print the amount of wealth left after the $K$ thefts. If Robin Hood cannot perform that many thefts, print impossible.

Constraints

$1 \le N, K \le 10^5$
$1 \le P_i \le 10^9$

Examples3

Example 1
Input
```
4 2
100 120 250 13
```
Expected output
```
100 120 50 13
```
Example 2
Input
```
4 4
100 120 250 13
```
Expected output
```
impossible
```
Example 3
Input
```
3 4
200 300 300
```
Expected output
```
100 100 200
```