题目内容

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$。你需要从原序列中按顺序选出恰好 $k$ 个元素，构成一个子序列。如果在这个子序列中，每一对相邻元素的最大公约数（$\gcd$）都大于 $1$，则称该子序列是相容的。

请你找出所有相容子序列中，最大元素的最小可能值。如果不存在任何相容子序列，则输出 $-1$。

序列长度 $n$ 满足 $2 \le n \le 2 \times 10^5$，需选取的元素个数 $k$ 满足 $1 \le k \le n$。序列中的每个整数 $a_i$ 均在 $1$ 到 $10^9$ 之间。

输入描述

第一行包含两个整数 $n$ 和 $k$，分别表示序列长度和需要选出的子序列长度。 第二行包含 $n$ 个整数，依次为 $a_1, a_2, \dots, a_n$。

输出描述

输出一个整数，表示所有合法相容子序列中最大元素的最小可能值；如果不存在，输出 $-1$。

样例1

输入

5 3
2 4 6 5 10

输出

6

说明

需要选出恰好 3 个元素。考察子序列 2, 4, 6： $\gcd(2,4)=2>1$，$\gcd(4,6)=2>1$，满足相容条件，最大值为 6。 其他合法子序列如 2, 6, 10 的最大值为 10，大于 6。因此最小可能的最大值是 6。

样例2

输入

4 2
2 3 5 7

输出

-1

说明

需要选出 2 个元素。序列中任意两个不同元素的 $\gcd$ 均为 1，不存在满足“每一对相邻元素 $\gcd > 1$”的子序列，因此无解，输出 -1。

样例3

输入

4 2
1 2 3 4

输出

4

说明

需要选出 2 个元素。注意 1 与任何整数的 $\gcd$ 都是 1，不能出现在长度 $\ge 2$ 的相容子序列中。 剩余可选元素为 2, 3, 4：

• 2 与 3 的 $\gcd=1$，不合法；
• 3 与 4 的 $\gcd=1$，不合法；
• 2 与 4 的 $\gcd(2,4)=2>1$，合法，最大值为 4。 因此答案为 4。

样例4

输入

3 1
9 5 7

输出

5

说明

当 k = 1 时，只需选出 1 个元素，没有相邻约束。因此直接选择序列中最小的元素即可，最小值为 5。