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 he can afford. Every contribution will be a multiple of 1 cent, i.e., nobody can pay
fractions of a cent.
Everybody writes down the maximum amount he is 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 [1/n]-th of the total cost. In case of a
tie, minimize the second largest distance, and so on. Since the smallest unit of
contribution is 1 cent, there might be more than one possible division of the cost.
In that case, 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, it is your task to figure out how much everybody
has to pay (including you).
Input
On the first line a positive integer: the number of test cases, at
most 100. After that per test case:
One line with two integers p and n: the price of the present in cents (1 ≤ p ≤ 1 000 000) and
the number of people (2 ≤ n ≤ 100) who contribute to the present (including you).
One line with n integers ai (1 ≤ ai ≤ 1 000 000), where
ai is the maximum amount, in cents, that the i-th person on the list is able to contribute.
Output
Per test case:
One line with n 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.