The greatest common divisor of a non-empty collection of natural numbers A is the maximum natural number d such that it is simultaneously a divisor of all numbers in the set A.
Given an array of natural numbers [a
1, a
2, . . . , a
n] and number k. It is required to choose a subarray of k consecutive elements [a
l, a
l+1, . . . , a
l+k−1] so that their greatest common divisor is as large as possible, and output this greatest common divisor.
Input
The first input line contains two integers n and k (2 ≤ n ≤ 500 000, 2 ≤ k ≤ n).
The second line contains n natural numbers a
1, a
2, . . . , a
n (1 ≤ a
i ≤ 10
18).
Imprint
Print one natural number — the maximum possible value of the greatest common divisor of the elements of a subarray of length k of the given array.
Examples
# |
Input |
Output |
1 |
10 4
2 3 4 8 12 6 12 18 4 3
| 6 |