Shohag 有一个整数 $$$n$$$ 和一组 $$$S$$$ 的 $$$m$$$ 唯一整数。帮助他找到按字典顺序最大的$$$^{\text{*}}$$$整数数组$$$a_1, a_2, \ldots, a_n$$$,使得$$$a_i \in S$$$ 对于每个$$$1 \le i \le n$$$ 和$$$a_{\operatorname{gcd}(i, j)} \neq \operatorname{gcd}(a_i, a_j)$$$$$$^{\text{†}}$$$ 对所有对 $$$1 \le i \lt j \le n$$$ 都满足,或者声明不存在这样的数组。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 10^5$$$)。
第二行包含 $$$m$$$ 按升序排列的唯一整数,表示集合 $$$S$$$ 的元素($$$1 \le x \le n$$$ 对于每个 $$$x \in S$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,如果没有解决方案,则打印 $$$-1$$$,否则打印 $$$n$$$ 整数 - 满足条件的按字典顺序最大的整数数组。
示例
输入 #1
3 6 3 3 4 6 1 1 1 2 1 2
输出 #1
6 4 4 3 4 3 1 -1
注意
在第一个测试用例中,数组中的每个元素都属于给定集合 $$$S = \{3, 4, 6\}$$$,并且数组的所有索引对都满足必要条件。特别是,对于 $$$(2, 3)$$$、$$$a_{\operatorname{gcd}(2, 3)} = a_1 = 6$$$ 和 $$$\operatorname{gcd}(a_2, a_3) = \operatorname{gcd}(4, 4) = 4$$$,因此它们不相等。还有其他数组也满足条件,但这个数组是其中按字典顺序最大的数组。
在第三个测试用例中,没有可能的解决方案,因为我们只允许使用 $$$a = [2, 2]$$$ 但对于这个数组,对于 $$$(1, 2)$$$, $$$a_{\operatorname{gcd}(1, 2)} = a_1 = 2$$$ 和 $$$\operatorname{gcd}(a_1, a_2) = \operatorname{gcd}(2, 2) = 2$$$,所以它们相等,这是不允许的!