ASD and FGH are playing a game in which both take turns and asks each other to solve a Problem.Now it is ASD's turn.So ASD asked FGH to solve the following problem.He gave FGH an Array A containing N positive integers A1,A2,A3,.....,AN and asked him to calculate \(MGCD_{\text{K}}(A)\).
Here \(MGCD_{\text{K}}(A)\) is the Modified GCD of Order K for Array A.
Modified GCD of Order K for an array is the Maximum number that divides at least \(Ceil(N/K) \) number of elements of the array.For example Modified Gcd of Order 2 for array A is the Maximum number that divides at least half of its elements.
Here Ceil(x) means,x rounded up to the nearest positive integer.Ceil Function
FGH is unable solve this Problem and is asking for your help.Help him.
INPUT:
- First line Contains two Positive Integers N and K.
- Second line contains N positive Integers A1,A2,A3.....AN,The Elements of Array A
OUTPUT:
Print a single line Containg a Positive Integer \(MGCD_{\text{K}}(A)\).
CONSTRAINTS:
\(1\le N \le 10^{5}\)
\(1\le K \le 5\)
\(1\le A_{i} \le 10^{12}\)