您已被邀请玩游戏。在这个游戏中,有 $$$n$$$ 可能的结果,对于每个结果,您必须下注一定整数的硬币。如果第 $$$i$$$ 结果获胜,您将收到等于您对该结果的赌注乘以 $$$k_i$$$ 的硬币数量。请注意,$$$n$$$ 结果中只有一个会获胜。
你的任务是确定如何分配硬币,以便在任何获胜结果的情况下你都能领先。更正式地说,您对所有结果下注的硬币总数必须严格小于每个可能获胜结果收到的硬币数量。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) - 结果的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$k_1,k_2,\ldots,k_n$$$ ($$$2 \le k_i \le 20$$$) - 如果第 $$$i$$$ 结果获胜,则为硬币数量的乘数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果无法按要求分配硬币,则输出$$$-1$$$。否则,输出 $$$n$$$ 整数 $$$x_1, x_2,\ldots, x_n$$$ ($$$1 \le x_i \le 10^{9}$$$) — 您对结果的赌注。
可以证明,如果存在解,则总有一个解满足这些约束。
如果有多个合适的解,则输出其中任意一个。
示例
输入 #1
6 3 3 2 7 2 3 3 5 5 5 5 5 5 6 7 9 3 17 9 13 3 6 3 2 5 9 4 6 8 3
输出 #1
27 41 12 1 1 -1 1989 1547 4641 819 1547 1071 -1 8 18 12 9 24
注意
在第一个测试用例中,硬币可以按如下方式分配:第一个结果为 $$$27$$$ 硬币,第二个结果为 $$$41$$$ 硬币,第三个结果为 $$$12$$$ 硬币。那么所有结果下注的硬币总数为 $$$27 + 41 + 12 = 80$$$ 硬币。如果第一个结果获胜,您将收到 $$$3 \cdot 27 = 81$$$ 硬币,如果第二个结果获胜,您将收到 $$$2 \cdot 41 = 82$$$ 硬币,如果第三个结果获胜,您将收到 $$$7 \cdot 12 = 84$$$ 硬币。所有这些值都严格大于 $$$80$$$。
在第二个测试用例中,一种方法是对每个结果下注一枚硬币。