题目内容

给定长度为 $n$ 的数组 $a$，小C想选出一个长度为 $k$ 的子序列。

所选子序列需满足相邻两个元素的 $gcd$ 不为 $1$。具体地，若选取下标序列 $i_1 < i_2 < \dots < i_k$，则需要满足：$gcd(a_{i_j}, a_{i_{j+1}}) > 1$（$1 \le j < k$）。

在所有满足上述条件的子序列中，求最大元素的最小可能取值。

如果不存在满足条件的子序列，则输出 $-1$。

【名词解释】

• 子序列：从原序列中删除任意个（可以为零）元素得到的新序列。
• $gcd$：即最大公因数，指两个整数共有约数中最大的一个。例如，$gcd(12, 30) = 6$。

输入描述

第一行输入两个整数 $n, k$（$1 \le k \le n$；$2 \le n \le 2 \times 10^5$），分别表示数组长度和所选子序列长度。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组元素的值。

输出描述

输出一个整数，表示满足条件的子序列中，最大元素的最小可能取值。

如果不存在满足条件的子序列，则输出 $-1$。

样例1

输入

5 3
2 4 3 9 6

输出

6

说明

• 可选下标 $[1, 2, 5]$ 对应元素 $\{2, 4, 6\}$，此时 $gcd(2, 4) = 2 > 1$，$gcd(4, 6) = 2 > 1$，最大值为 $6$。
• 可知没有更小的最大值，因此输出 $6$。

样例2

输入

5 2
5 7 11 13 17

输出

-1

说明

在这个样例中，数组中任意两个元素的 $gcd$ 均为 $1$，无法选出符合条件的子序列，因此输出 $-1$。