今天是你的朋友的生日，你和其他一些人决定合资给他买一份《星际争霸II》（StarCraft II）作为礼物，因为谁会不想要这个呢？

你们同意尽可能公平地分摊费用。由于你们中有些人的预算比其他人更充裕，你们还同意没有人需要支付超过其承受能力的金额。每个人的出资额必须是 1 美分（cent）的倍数，也就是说，没有人可以支付不足 1 美分的零头。

每个人都写下自己能够出资的最大金额。在考虑了每个人的最大金额后，你们要尽可能公平地分摊礼物的总费用。这意味着，你们要最小化每个人的出资额与总费用的 $\frac{1}{n}$ 之间的最大距离（绝对差值）。如果出现平局，则最小化第二大的距离，依此类推（即按降序排列的绝对差值序列在字典序上最小）。由于最小出资单位是 1 美分，因此可能存在多种可能的费用分配方案。在这种情况下，最大出资限额较高的人支付更多。如果仍然存在歧义，则在列表中排在前面的人支付更多。

既然是你买了礼物，你的任务就是计算出每个人（包括你）需要支付多少钱。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100。接下来的每个测试用例包含：

• 一行，包含两个整数 $p$ 和 $n$：礼物的价格（单位：美分，$1 \le p \le 1\,000\,000$）和共同出资的人数（包括你，$2 \le n \le 100$）。
• 一行，包含 $n$ 个整数 $a_i$（$1 \le a_i \le 1\,000\,000$），其中 $a_i$ 是列表中第 $i$ 个人能够出资的最大金额（单位：美分）。

输出格式

对于每个测试用例：

• 输出一行，包含 $n$ 个整数：根据上述方案每个人需要出资的金额。如果无法按照上述规则分摊总费用，则该行应输出 IMPOSSIBLE。

样例

输入样例 1

3
20 4
10 10 4 4
7 3
1 1 4
34 5
9 8 9 9 4

输出样例 1

6 6 4 4
IMPOSSIBLE
8 7 8 7 4