G. Gold Experience
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим неориентированный граф $$$G$$$ из $$$n$$$ вершин. В каждой вершине расположено целое число $$$a_i$$$.

Две вершины $$$i$$$ и $$$j$$$ соединены ребром, если и только если $$$gcd(a_i, a_j) > 1$$$, где $$$gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

Рассмотрим множество вершин. Скажем, что вершина в этом множестве честная, если она соединена ребром со всеми остальными вершинами в этом множестве.

Вам нужно найти множество из $$$k$$$ вершин ($$$k$$$ — фиксированное целое число, $$$2 \cdot k \le n$$$) такое, что в нём все вершины честные или все вершины не являются честными. Можно показать, что хотя бы одно такое множество всегда существует.

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

Первая строка содержит целые числа $$$n$$$ и $$$k$$$ ($$$6 \leq 2 \cdot k \leq n \leq 10^5$$$) — the количество вершин и значение параметра $$$k$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \le a_i \le 10^7$$$) — значения, записанные в вершинах.

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

Выведите ровно $$$k$$$ различных целых чисел — индексы элементов в множестве в любом порядке.

Примеры
Входные данные
6 3
6 15 10 8 14 12
Выходные данные
1 3 6
Входные данные
8 4
11 15 10 6 21 15 10 6
Выходные данные
1 2 3 4
Входные данные
10 5
3003 17017 3230 49742 546 41990 17765 570 21945 36465
Выходные данные
4 6 9 10 1
Примечание

В первом примере, множество $$$\{2, 4, 5\}$$$ является примером множества без честных вершин. Видно, что вершина $$$2$$$ не имеет общего ребра с вершиной $$$4$$$, так как $$$gcd(15, 8) = 1$$$. Вершина $$$4$$$ не имеет общего ребра с вершиной $$$2$$$. Вершина $$$5$$$ не имеет общего ребра с вершиной $$$2$$$.

Во втором примере множество $$$\{8, 5, 6, 4\}$$$ является примером множества, где все вершины честные.