题目描述

你正在参加国际连续分隔大赛(International Continous Partition Contest, ICPC)，给定一个数列将其分割成 $k$ 段，记每段价值为该段所有数字的 GCD 值；求所有段价值中最小值的最大可能值。

形式化地，设

$$\operatorname{gcd}_{i=1}^n\left\{ a_i \right\} := \operatorname{gcd}\left( a_1,a_2,a_3,\cdots,a_n \right)$$

表示 $a_1,a_2,a_3,\cdots,a_n$ 的最大公因数，定义 $\gcd(a)=a$。数字 $b_{i,j}$ 表示分割后的第 $i$ 段的第 $j$ 个数，设

$$V=\operatorname{min}_{i=1}^k\left[ \operatorname{gcd}_{j=1}^n\left( b_{i,j} \right) \right]$$

求 $V$ 最大可能值。

输入描述

第一行输入两个空格隔开的整数 $n,k$ 表示数列中数字的个数 $n$ 与段数 $k$，满足 $1\leqslant k\leqslant n \leqslant 1\times 10^4$。

第一行输入 $n$ 个空格隔开的整数 $a_i$ 表示数列的数字，满足 $1\leqslant a_i \leqslant 1\times10^9$。

输出描述

输出一个整数表示所有段价值中最小值的最大可能值。

样例

5 4
1 14 514 1919 810

1

4 3
32 24 36 33

12