I - Maximum GCD Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

問題文

N 個の整数 A_1,A_2,\ldots,A_N が与えられます。

この中から K 個を選ぶとき、それらの最大公約数の最大値を求めてください。

制約

  • 1 \leq K \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^6
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \ldots A_N

出力

最大公約数の最大値を出力せよ。

入力例 1

3 2
2 3 4

出力例 1

2

2 と 4 を選んだとき最大公約数は 2 となり、最大です。

入力例 2

3 3
5 5 5

出力例 2

5

入力例 3

10 4
225707 265514 765350 617700 837712 187034 799142 35549 784661 961512

出力例 3

2

Problem Statement

You are given N integers A_1, A_2, \ldots, A_N.

Consider choosing K of them. Find the maximum possible greatest common divisor of the chosen integers.

Constraints

  • 1 \leq K \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^6
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the maximum possible greatest common divisor.

Sample Input 1

3 2
2 3 4

Sample Output 1

2

If you choose 2 and 4, the greatest common divisor will be 2, which is the maximum.

Sample Input 2

3 3
5 5 5

Sample Output 2

5

Sample Input 3

10 4
225707 265514 765350 617700 837712 187034 799142 35549 784661 961512

Sample Output 3

2