Birthday Gift

Time limit1sMemory limit128 MB

Summary

Assign integer payments capped by each friend's maximum so the sum equals the gift price while lexicographically minimizing sorted deviations from the fair share, breaking remaining ties by capacity and input order.

Level: Medium7 of 10
Topics: Greedy, Binary search, Sorting
Solved: No attempts yet

Problem

Today is Sunyoung's birthday, and her friends have decided to buy her StarCraft II as a birthday gift.

The friends want to split the cost fairly. Because they are not equally well off, no one pays more than the maximum amount they can afford. Everyone pays an integer number of won (fractional amounts are not allowed), and everyone pays at least $1$ won.

If the gift costs $p$ and there are $n$ friends, each person's fair share is $p / n$ . To split the cost fairly, we minimize the maximum over all people of the difference between the amount a person pays and $p / n$ . If several ways tie on this maximum, we then minimize the next largest difference, then the one after that, and so on.

Because each person only has to pay at least $1$ won, several payment plans may satisfy the rule above. In that case, a person who can afford more (a larger maximum amount) pays more. If ties still remain, the person earlier in the list pays more.

Given the maximum amount each friend can pay and the price of the gift, write a program that determines how much each person must pay. If there is no way to collect the price of the gift exactly, print IMPOSSIBLE instead.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 100$ )

Each test case consists of two lines. The first line contains the price of the gift $p$ and the number of friends $n$ , separated by a space. ( $1 \le p \le 1{,}000{,}000$ , $2 \le n \le 100$ ) The second line contains the maximum amounts $a_1, a_2, \dots, a_n$ that each friend can pay, separated by spaces. ( $1 \le a_i \le 1{,}000{,}000$ )

Output

For each test case, print on one line the amount each person must pay, in the input order, separated by spaces. If there is no fair way to collect the price of the gift, print IMPOSSIBLE on that line instead.

Examples8

Example 1

Input

Expected output

6 6 4 4
IMPOSSIBLE
8 7 8 7 4

Example 2
Input
```
1
8 4
2 2 2 2
```
Expected output
```
2 2 2 2
```
Example 3
Input
```
1
100 3
10 10 10
```
Expected output
```
IMPOSSIBLE
```
Example 4
Input
```
1
2 3
5 5 5
```
Expected output
```
IMPOSSIBLE
```
Example 5
Input
```
1
40 4
1 1 1 100
```
Expected output
```
1 1 1 37
```
Example 6
Input
```
1
10 4
5 5 5 5
```
Expected output
```
3 3 2 2
```
Example 7
Input
```
1
23 5
3 10 10 10 3
```
Expected output
```
3 6 6 5 3
```
Example 8
Input
```
1
30 3
10 10 10
```
Expected output
```
10 10 10
```