Greatest Common Divisor

Time limit1sMemory limit1024 MB

Summary

Given an array of n numbers and a window length k, find the largest GCD of any contiguous subarray of length k.

Level: Medium6 of 10
Topics: Sliding window, Number theory, Queue
Solved: No attempts yet

Problem

The greatest common divisor of a nonempty set $A$ of natural numbers is the largest natural number $d$ that divides every number in $A$ .

You are given an array of natural numbers $[a_1, a_2, \ldots, a_n]$ and an integer $k$ . Choose a contiguous subarray $[a_l, a_{l+1}, \ldots, a_{l+k-1}]$ of length $k$ so that its greatest common divisor is as large as possible, and output that value.

Input

The first line contains two integers $n$ and $k$ ( $2 \le n \le 500\,000$ , $2 \le k \le n$ ).

The second line contains $n$ natural numbers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^{18}$ ).

Output

Print one natural number: the maximum possible greatest common divisor of a subarray of length $k$ .

Examples1

Example 1
Input
```
10 4
2 3 4 8 12 6 12 18 4 3
```
Expected output
```
6
```