← 返回题目列表

Codeforces · 2131/H

H. 海、你和 copriMe

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

给 Umi 一个长度为 $$$n$$$ 的数组 $$$a$$$,其元素是 $$$1$$$ 和 $$$m$$$ 之间的整数。她喜欢互质整数并想找到四个 不同 索引 $$$p, q, r, s$$$ ($$$1 \le p, q, r, s \le n$$$),使得 $$$\gcd(a_p, a_q) = 1$$$ 和 $$$\gcd(a_r, a_s) = 1$$$$$$^{\text{*}}$$$。

如果有多个解,可以输出其中任意一个。

$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$4 \le n \le 2 \cdot 10^5, 1 \le m \le 10^6$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le m$$$)。

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

输出

对于每个测试用例:

  • 如果不存在这样一组四个不同索引,则输出一个整数 $$$0$$$。
  • 否则,输出四 不同 满足条件的整数 $$$p, q, r, s$$$ ($$$1 \le p, q, r, s \le n$$$)。如果有多个解,则输出其中任意一个。

示例

输入
复制

5
4 15
4 7 9 15
4 10
1 2 4 8
5 15
6 10 11 12 15
5 15
6 10 11 14 15
6 10000
30 238 627 1001 1495 7429

输出
复制

1 3 2 4
0
0
3 1 4 5
1 4 2 3

注意

在第一个测试用例中, $$$\gcd(a_1, a_3) = \gcd(4, 9) = 1$$$, $$$\gcd(a_2, a_4) = \gcd(7, 15) = 1$$$。

在第二个测试用例中,可以证明不存在这样的四元组。