H. Взаимнопростые пары
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Уми дан массив $$$a$$$ длиной $$$n$$$, элементы которого являются целыми числами от $$$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$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Во втором наборе входных данных можно показать, что такой четверки не существует.