← 返回题目列表

Codeforces · 1945/H

H. GCD 更大

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

在徒步旅行的晚上,Kirill 和 Anton 决定从背包中取出一个长度为 $$$n$$$ 的整数数组 $$$a$$$ 并用它玩一个游戏。规则如下:

1. Kirill 从 $$$2$$$ 到 $$$(n-2)$$$ 数字中选择并用红色圈出它们。
2. Anton 用蓝色圈出所有剩余的数字。
3. Kirill 计算所有红色数字的最大公约数 (GCD)。
4. Anton 计算所有蓝色数字的按位与,并将数字 $$$x$$$ 添加到结果中。
5. 如果所有红色数字的 GCD 严格大于所有蓝色数字与数字 $$$x$$$ 的按位与之和,则基里尔获胜;否则,安东获胜。

帮助基里尔击败安东或告诉他这是否不可能。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 20\,000$$$) - 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$4\le n \le 4\cdot 10^5$$$, $$$0 \le x \le 4\cdot 10^5$$$) - 分别是整数的数量和数量 $$$x$$$。

第二行包含一个长度为 $$$n$$$ 的数组 $$$a$$$ ($$$1 \le a_i \le 4\cdot 10^5$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$4\cdot 10^5$$$。还保证每个测试用例的$$$a_i$$$的最大值之和不超过$$$4\cdot 10^5$$$。

输出

对于每个测试用例,如果满足条件,则在第一行输出“YES”,在第二行输出Kirill选择的数字的个数以及以空格分隔的任意顺序的数字本身,在第三行输出第二组的大小及其中的数字。

否则,输出“NO”。

您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。

示例

输入 #1

8
4 1
4 3 1 8
4 1
4 5 8 4
5 0
1 1 1 1 1
5 2
31 63 127 63 31
4 1
1 3 3 3
8 3
4 3 4 1 2 2 5 3
4 2
1 4 3 6
8 48
31 61 37 15 53 26 61 12

输出 #1

YES
2 4 8
2 3 1 
YES
2 4 4
2 5 8 
NO
YES
2 63 63
3 31 127 31
YES
2 3 3
2 1 3
YES
2 4 4
6 3 1 2 2 5 3
YES
2 3 6
2 1 4 
YES
2 61 61
6 31 37 15 53 26 12