考虑一个具有 $$$n$$$ 顶点的无向图 $$$G$$$。每个顶点都有一个值$$$a_i$$$。
两个顶点 $$$i$$$ 和 $$$j$$$ 通过边连接当且仅当 $$$gcd(a_i, a_j) > 1$$$,其中 $$$gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。
考虑一组顶点。如果该集合中的某个顶点与该集合中所有其他顶点的边相连,我们称该顶点为公平的。
您需要找到一组 $$$k$$$ 顶点(其中 $$$k$$$ 是给定整数,$$$2 \cdot k \le n$$$),其中所有顶点都是公平的或所有顶点都不公平。人们可以证明这样一个集合总是存在。
输入
第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$6 \leq 2 \cdot k \leq n \leq 10^5$$$) — 顶点数和参数 $$$k$$$。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \le a_i \le 10^7$$$) - 顶点中的值。
输出
精确打印 $$$k$$$ 个不同的整数 - 所选集合中顶点的索引(按任意顺序)。
示例
输入 #1
6 3 6 15 10 8 14 12
输出 #1
1 3 6
输入 #2
8 4 11 15 10 6 21 15 10 6
输出 #2
1 2 3 4
输入 #3
10 5 3003 17017 3230 49742 546 41990 17765 570 21945 36465
输出 #3
4 6 9 10 1
注意
在第一个测试用例中,集合 $$$\{2, 4, 5\}$$$ 是集合中没有公平顶点的示例。由于 $$$gcd(15, 8) = 1$$$,顶点 $$$2$$$ 不与顶点 $$$4$$$ 共享边。顶点 $$$4$$$ 不与顶点 $$$2$$$ 共享边。顶点 $$$5$$$ 不与顶点 $$$2$$$ 共享边。
在第二个测试用例中,集合 $$$\{8, 5, 6, 4\}$$$ 是所有顶点都是公平的集合的示例。