Problem B
Keep it Cool

Picture by Fitness First via Vimeo, cc by

You can only refill the fridge from the front, so in an ideal world, you would first take out all the sodas currently in the fridge, then put in the $n$ new ones, and then put the old and cold sodas in front of the new ones. But in an ideal world you would also not have two exams and a homework deadline coming. You are simply way too busy to do all this work.

Instead, you are going to just put the new bottles in the front of the fridge and hope for the best. However, you can still to be clever about which slots to put the new sodas in. Each time a student comes for a soda, they will take one from the front of a uniformly random non-empty slot in the fridge. You decide to add the new bottles to the fridge so as to maximize the probability that all the next $m$ students getting a soda from the fridge will get a cold one.

Input

The first line of input contains four integers $n$, $m$, $s$ and $d$ ($1 \le n, m, s, d \le 100$), the number of new soda bottles, number of students to optimize for, number of slots in the fridge, and capacity of each slot, respectively. Then follows a line containing $s$ integers $c_1, \ldots , c_ s$ ($0 \le c_ i \le d$ for each $i$), where $c_ i$ is the number of soda bottles currently in slot $i$ of the fridge.

You may assume that there is free space for all the $n$ new bottles in the fridge.

Output

If there is a chance that all the next $m$ students will get a cold bottle, then output $s$ integers describing a refill scheme for the $n$ soda bottles that maximizes the probability of this happening. The $i^{\text {th}}$ of these $s$ integers indicates how many of the new bottles are placed in the front of slot $i$ in the fridge. If there are multiple optimal refill schemes, output any one of them. Otherwise, if it is impossible for all the next $m$ students to get a cold soda, output “impossible” instead.

5 3 3 4
0 1 4

2 3 0

2 7 6 4
0 1 2 2 0 1

impossible