Рассмотрим неориентированный граф \(G\) из \(n\) вершин. В каждой вершине расположено целое число \(a_i\).
Две вершины \(i\) и \(j\) соединены ребром, если и только если \(gcd(a_i, a_j) > 1\), где \(gcd(x, y)\) обозначает наибольший общий делитель (НОД) чисел \(x\) и \(y\).
Рассмотрим множество вершин. Скажем, что вершина в этом множестве честная, если она соединена ребром со всеми остальными вершинами в этом множестве.
Вам нужно найти множество из \(k\) вершин (\(k\) — фиксированное целое число, \(2 \cdot k \le n\)) такое, что в нём все вершины честные или все вершины не являются честными. Можно показать, что хотя бы одно такое множество всегда существует.
Выходные данные
Выведите ровно \(k\) различных целых чисел — индексы элементов в множестве в любом порядке.
Примечание
В первом примере, множество \(\{2, 4, 5\}\) является примером множества без честных вершин. Видно, что вершина \(2\) не имеет общего ребра с вершиной \(4\), так как \(gcd(15, 8) = 1\). Вершина \(4\) не имеет общего ребра с вершиной \(2\). Вершина \(5\) не имеет общего ребра с вершиной \(2\).
Во втором примере множество \(\{8, 5, 6, 4\}\) является примером множества, где все вершины честные.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
6 15 10 8 14 12
|
1 3 6
|
|
2
|
8 4
11 15 10 6 21 15 10 6
|
1 2 3 4
|
|
3
|
10 5
3003 17017 3230 49742 546 41990 17765 570 21945 36465
|
4 6 9 10 1
|