← 返回题目列表

Codeforces · 2173/C

C. 奏的完美倍数

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

那些记忆,我们都刻在了自己身上……无论多么辛苦,都是我们走过的人生!
— 天使节拍!

在来世学校,奏学习一种奇特的数字游戏。

她给你两个整数 $$$n$$$ 和 $$$k$$$,以及一个由 $$$n$$$ 整数组成的数组 $$$a$$$,其中 $$$1 \le a_i \le k$$$ 成立。

对于整数集合 $$$B = \{b_1, b_2, \ldots, b_m\}$$$ 其中 $$$1\le b_i\le k$$$,我们称之为 完成 当且仅当 以下两项均成立:

  • 对于每个 $$$1\le i\le n$$$,$$$a_i$$$ 中至少包含一个除数 $$$B$$$;
  • 对于每个 $$$1\le j\le m$$$,$$$b_j$$$ 小于或等于 $$$k$$$ 的所有正倍数在数组 $$$a$$$ 中至少出现一次。

你必须找到一个 完成 设置 $$$B$$$ 为 最小值 可能的大小,或确定不存在这样的集合。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$1\le k\le 10^9$$$) - $$$a$$$ 的长度和 $$$a$$$ 元素的上限。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le k$$$) — $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例:

  • 如果没有 完成 设置$$$B$$$存在,在输出的唯一行中打印单个整数$$$-1$$$。
  • 否则:
    • 首先在输出的第一行打印一个整数 $$$m$$$ ($$$1\le m\le n$$$) — $$$B$$$ 的大小。请注意,您必须最小化 $$$B$$$ 的大小。
    • 然后在第二行输出 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le k$$$) — 您构建的集合。

如果有多个答案,您可以打印其中任何一个。

示例

输入
复制

4
4 6
3 2 4 6
5 5
1 2 3 4 5
3 6
2 3 6
1 2
2

输出
复制

2
2 3
1
1
-1
1
2

注意

在第一个测试用例中, $$$B=\{2,3\}$$$ 有效。对于$$$b=2$$$,所有倍数$$$\{2,4,6\}$$$(最多$$$k=6$$$)出现在$$$a$$$中;对于 $$$b=3$$$,出现倍数 $$$\{3,6\}$$$。每个 $$$a_i$$$ 都可以被 $$$2$$$ 或 $$$3$$$ 整除。没有任何一个 $$$b$$$ 可以同时满足这两个条件,因此 $$$m=2$$$ 是最小的。

在第二个测试用例中, $$$B=\{1\}$$$ 满足这两个规则,因为每个数字都可以被 $$$1$$$ 整除,并且出现 $$$1$$$ 到 $$$k$$$ 的所有倍数。