← 返回题目列表

Codeforces · 2039/D

D. Shohag 喜欢 GCD

中文机器翻译题面 查看原题

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$$$,所以它们相等,这是不允许的!