Keep it Cool

As the semester workload ramps up, you have to refill the lab fridge with soda. The fridge has $s$ slots, each with a capacity for $d$ bottles of soda, and you have $n$ new soda bottles to add. The sodas already in the fridge are nice and cold, but the new ones are not. They need to stay in the fridge for a while before they are ready to drink.

You can only refill the fridge from the front. In an ideal world, you would take out all the sodas currently in the fridge, put in the $n$ new ones, and then put the old cold sodas in front of the new ones. But you have two exams and a homework deadline coming up, so you do not have time for all that work.

Instead, you put the new bottles in the front of the fridge and hope for the best. You can still choose which slots receive the new sodas. Each time a student comes for a soda, they take one from the front of a uniformly random non-empty slot. You decide where to add the new bottles to maximize the probability that all of the next $m$ students get a cold one.

The first line contains four integers $n$, $m$, $s$, and $d$ ($1 \le n, m, s, d \le 100$), the number of new soda bottles, the number of students to optimize for, the number of slots, and the capacity of each slot. The second line contains $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$.

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

If there is a chance that all of the next $m$ students get a cold bottle, output $s$ integers describing a refill scheme for the $n$ soda bottles that maximizes the probability of this. The $i$-th integer is the number of new bottles placed in the front of slot $i$. If several refill schemes are optimal, output any one of them. Otherwise, if it is impossible for all of the next $m$ students to get a cold soda, output "impossible".