CF2131H Sea, You & copriMe

Umi is given an array $$$a$$$ of length $$$n$$$, whose elements are integers between $$$1$$$ and $$$m$$$. She loves coprime integers and wants to find four distinct indices $$$p, q, r, s$$$ ($$$1 \\le p, q, r, s \\le n$$$), such that $$$\\gcd(a\_p, a\_q) = 1$$$ and $$$\\gcd(a\_r, a\_s) = 1$$$ $$$^{\\text{∗}}$$$. If there are multiple solutions, you may output any one of them. $$$^{\\text{∗}}$$$ $$$\\gcd(x, y)$$$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $$$x$$$ and $$$y$$$.

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 $$$m$$$ ($$$4 \\le n \\le 2 \\cdot 10^5, 1 \\le m \\le 10^6$$$). The second line of each test case contains $$$n$$$ integers $$$a\_1, a\_2, \\dots, a\_n$$$ ($$$1 \\le a\_i \\le m$$$). It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \\cdot 10^5$$$, and that the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

For each test case: - If no such set of four distinct indices exists, output one integer $$$0$$$. - Otherwise, output four distinct integers $$$p, q, r, s$$$ ($$$1 \\le p, q, r, s \\le n$$$) that satisfy the condition. If there are multiple solutions, output any one of them.

In the first test case, $$$\\gcd(a\_1, a\_3) = \\gcd(4, 9) = 1$$$, $$$\\gcd(a\_2, a\_4) = \\gcd(7, 15) = 1$$$. In the second test case, it can be shown that no such quadruple exists.