说明

天依决定了 $n$ 个素材，它们将依次在作文中被叙写。其中，第 $i$ 个素材的立意特征值是 $a_i$。

但天依发现她构思的大作实在是太长啦，所以她想把它们划分为恰好 $k$ 个章节，每个章节包含一段连续且非空的素材。假设第 $i$ 个章节包含素材 $[l_i,r_i]$，天依将选取立意特征值最大的素材来升华，得到该章节的立意值 $b_i$，满足 $b_i=\max\limits_{i\in[l_i,r_i]}\{a_i\}$。

最后，整篇作文的凝练度为每个章节立意值的最大公约数，即 $\gcd\limits_{i\in[1,k]}\{b_i\}$。

天依当然希望最大化作文的凝练度，那么凝练度的最大值是多少呢？

简化题意

有一个长度为 $n$ 的序列 $a$。要求将这个序列恰好分成连续且非空的 $k$ 段，并定义第 $i$ 段的立意值为该段的所有元素的最大值，记为 $b_i$。要求最大化 $\gcd\limits_{i\in[1,k]}\{b_i\}$ 并输出这个最大值。

输入格式

第一行包含两个整数 $n,k$，表示素材的长度和需要划分的章节数。

接下来第二行包含 $n$ 个整数，表示每个素材的立意特征值。

输出格式

一行一个整数，表示你的答案。

5 3
1 3 2 9 6

3

5 2
10 2 5 5 5

5

提示

样例解释 1

最优的素材划分可能有多种，这里给出一种最优的素材划分，将这 $5$ 个素材分成 $3$ 个章节：$[1,3],[2,9],[6]$，可以得出 $b_1=3,b_2=9,b_3=6$，凝练度的最大值为 $\gcd(3,9,6)=3$。

数据规模与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le k\le n\le 10^5$，$1\le a_i\le 10^{6}$。