#CF1945H. GCD 更大

    ID: 6541 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>搜索枚举数据结构其他数学数论*2600

GCD 更大

H. GCD 更大

单个测试点时间限制33单个测试点内存限制512512 兆字节

徒步旅行的晚上,基里尔和安东从背包里拿出一个长度为 nn 的整数数组 aa,并用它玩一个游戏。规则如下:

  1. 基里尔从中选择 22n2n-2 个数字,用红色圈出。
  2. 安东把剩下所有数字用蓝色圈出。
  3. 基里尔计算所有红色数字的最大公约数 gcd\gcd
  4. 安东计算所有蓝色数字的按位与 AND\operatorname{AND},并在结果上加上数字 xx
  5. 如果红色数字的 gcd\gcd 严格大于(蓝色数字的按位与 +x+x),则基里尔获胜;否则安东获胜。

请帮助基里尔找到一种获胜方案,或者输出无解。


输入格式

输入包含多组测试数据。 第一行一个整数 tt1t2×1041\le t\le 2\times10^4),表示测试用例数量。

每组测试用例: 第一行两个整数 nnxx4n4×1054\le n\le 4\times10^50x4×1050\le x\le 4\times10^5)。 第二行长度为 nn 的数组 aa1ai4×1051\le a_i\le 4\times10^5)。

保证所有测试用例的 nn 之和不超过 4×1054\times10^5; 同时保证所有测试用例的 aia_i 最大值之和不超过 4×1054\times10^5


输出格式

如果存在合法方案:

  • 第一行输出 YES
  • 第二行输出基里尔选的数字个数, followed by 这些数字
  • 第三行输出安东的数字个数, followed by 这些数字

否则输出 NO

大小写不敏感。


样例输入

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

样例输出

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