H. Sea, You & copriMe
brute force; constructive algorithms; graphs; greedy; math; number theory
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) 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.