Problem D
Film Critics
There are $n$ critics numbered from $1$ to $n$ scheduled to watch the movie early, and each of them will watch it separately. After watching it, they will immediately give it a score from $0$ to $m$. Susan, the cinema owner, has carefully looked at every critic’s social media and already knows that the $i$th critic thinks the movie is worth a score of $a_ i$. However, the $i$th critic will not simply give the movie a score of $a_ i$ like you would expect, because they also take into account the scores that the other critics gave. Here is how they behave:
-
The first critic to arrive will be so happy that they are the first to review the movie that they will give it a score of $m$ regardless of their initial opinion.
-
Every subsequent critic will look at the average score given by the previous critics. If this number is smaller than or equal to the initial opinion $a_ i$ then the critic will give it a score of $m$, otherwise they will give it a $0$.
Susan thinks the critics’ behaviour is ridiculous. She has watched the movie, and it is clearly worth a score of exactly $k/n$ and nothing else! But Susan is the owner of the cinema, so she gets to decide in what order to invite the critics. Your task is to find a permutation of $1,2, \dots , n$ so that if the critics arrive in this order the average score will be exactly $k/n$.
Input
The first line of input contains three integers $n$, $m$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq 10^4$, $0 \leq k \leq n \cdot m$). The second line contains the $n$ integers $a_1, a_2, \ldots , a_ n$ ($0 \le a_ i \le m$ for each $i$), the $n$ critic scores as described above.
Output
If the critics can be ordered in such a way that the resulting average score is exactly $k/n$, then output $n$ integers $p_1, \ldots , p_ n$ ($1 \le p_ i \le n$), where $p_ i$ indicates that the $i$th critic to visit the cinema is the critic numbered $p_ i$. This list of integers should be a permutation such that the average score given by the critics is $k/n$. If there are multiple solutions any one will be accepted.
Otherwise, if there is no such way to order the critics, output “impossible”.
Sample Input 1 | Sample Output 1 |
---|---|
5 10 30 10 5 3 1 3 |
3 5 2 1 4 |
Sample Input 2 | Sample Output 2 |
---|---|
5 5 20 5 3 3 3 3 |
impossible |