CF2173C.Kanade's Perfect Multiples

We've carved those memories into ourselves... No matter how hard they were, they're the lives we carried out!

— Angel Beats!

In the afterlife school, Kanade studies a peculiar number game.

She gives you two integers $n$ and $k$, as well as an array $a$ consisting of $n$ integers, where $1 \le a_i \le k$ holds.

For an integer set $B = {b_1, b_2, \ldots, b_m}$ where $1\le b_i\le k$, we call it complete if and only if both of the following hold:

• For each $1\le i\le n$, at least one divisor of $a_i$ is contained in $B$;
• For each $1\le j\le m$, all positive multiples of $b_j$ which are less than or equal to $k$ appear in the array $a$ at least once.

You have to find a complete set $B$ with minimum possible size, or determine that no such set exists.

我们将那些记忆刻入了自身……无论它们多么艰难，那都是我们曾活过的人生！

——《Angel Beats！》

在来世的学校里，神山同学正在研究一个奇特的数字游戏。

她给你两个整数 $n$ 和 $k$，以及一个由 $n$ 个整数组成的数组 $a$，其中对每个 $i$ 均满足 $1 \le a_i \le k$。

对于一个整数集合 $B = \{b_1, b_2, \ldots, b_m\}$（其中 $1\le b_i\le k$），当且仅当同时满足以下两个条件时，称其为完备的（complete）：

• 对每个 $1\le i\le n$，$a_i$ 的至少一个正因数属于 $B$；
• 对每个 $1\le j\le m$，所有不超过 $k$ 的 $b_j$ 的正倍数，均在数组 $a$ 中至少出现一次。

你需要找出一个大小最小的完备集合 $B$；若不存在这样的集合，则判定其不存在。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1\le n\le 2\cdot 10^5$, $1\le k\le 10^9$) — the length of $a$ and the upper bound of elements of $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le k$) — the elements of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case:

• If no complete set $B$ exists, print a single integer $-1$ in the only line of output.
• Otherwise:
  • First print a single integer $m$ ($1\le m\le n$) in the first line of output — the size of $B$. Note that you have to minimize the size of $B$.
  • Then output $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \le b_i \le k$) in the second line — the set you constructed.

If there are multiple answers, you may print any of them.

对于每个测试用例：

• 如果不存在完整的集合 $B$，则在输出的唯一一行中打印单个整数 $-1$。
• 否则：
  • 首先在输出的第一行中打印单个整数 $m$（$1\le m\le n$）——即集合 $B$ 的大小。注意，你需要最小化 $B$ 的大小。
  • 然后在第二行输出 $m$ 个整数 $b_1, b_2, \ldots, b_m$（$1 \le b_i \le k$）——即你构造出的集合。

如果存在多个答案，你可以输出其中任意一个。

In the first test case, $B={2,3}$ works. For $b=2$, all multiples ${2,4,6}$ (up to $k=6$) appear in $a$; for $b=3$, multiples ${3,6}$ appear. Every $a_i$ is divisible by $2$ or $3$. No single $b$ can satisfy both conditions, so $m=2$ is minimal.

In the second test case, $B={1}$ satisfies both rules since every number is divisible by $1$ and all multiples of $1$ up to $k$ appear.

在第一个测试用例中，集合 $B={2,3}$ 满足条件。对于 $b=2$，所有不超过 $k=6$ 的倍数 ${2,4,6}$ 均出现在序列 $a$ 中；对于 $b=3$，其不超过 $k=6$ 的倍数 ${3,6}$ 也均出现在 $a$ 中。序列中的每个元素 $a_i$ 均能被 $2$ 或 $3$ 整除。不存在单个 $b$ 能同时满足上述两个条件，因此最小的 $m$ 为 $2$。

在第二个测试用例中，集合 $B={1}$ 满足两个条件：因为任意整数均可被 $1$ 整除，且所有不超过 $k$ 的 $1$ 的倍数（即 $1,2,\dots,k$）均出现在序列 $a$ 中。