Fair Division#2449
It's your friend's birthday, and you and some other people decided to buy him a copy of StarCraft II, because who wouldn't want to have that?
You agreed to divide the costs as fairly as possible. Since some of you have more money available than others, you also agreed that nobody has to pay more than they can afford. Every contribution will be a multiple of cent, i.e., nobody can pay fractions of a cent.
Everybody writes down the maximum amount they are able to contribute. Taking into account these maximum amounts from everybody, you share the cost of the present as fairly as possible. That means you minimize the largest distance of the contributions to -th of the total cost. In case of a tie, you minimize the second-largest distance, and so on. Since the smallest unit of contribution is cent, there might be more than one possible division of the cost. In that case, the persons with a higher maximum amount pay more. If there is still ambiguity, those who come first in the list pay more.
Since you bought the present, your task is to figure out how much everybody has to pay (including yourself).
The first line contains a positive integer: the number of test cases, at most . For each test case:
One line with two integers and : the price of the present in cents (1 \leq p \leq 1000000) and the number of people (2 \leq n \leq 100) who contribute to the present (including you).
One line with integers a_i (1 \leq a_i \leq 1000000), where a_i is the maximum amount, in cents, that the -th person in the list is able to contribute.
For each test case:
One line with integers: the amounts each person has to contribute according to the scheme. If the total cost cannot be divided according to the above rules, the line must contain "IMPOSSIBLE" instead.
Example 1