Primal Partitions

Time limit2sMemory limit256 MB

Summary

Split the array into k consecutive segments to maximize the smallest segment score, where each segment scores its largest common prime factor or zero.

Level: Hard8 of 10
Topics: Binary search, Dynamic programming, Number theory
Solved: No attempts yet

Problem

The math department challenged the computer science department to a puzzle in discrete mathematics.

You are given a sequence of $n$ positive integers. Split the sequence into $k$ consecutive regions. Every region holds at least one integer, and joining the regions in order gives back the original sequence.

A partition is scored like this. For each region, find the largest prime that divides every integer in that region. A prime is an integer greater than 1 whose only divisors are 1 and itself. If no prime divides every integer of the region, that region scores 0. The score of the partition is the smallest region score.

Find the largest score a partition into $k$ regions reaches.

Input

The first line contains the length of the sequence $n$ and the number of regions $k$ ( $1 \le n \le 20000$ , $1 \le k \le \min(100, n)$ ).

The second line contains the $n$ integers $v_1, v_2, \dots, v_n$ of the sequence, in order ( $1 \le v_i \le 1000000$ ).

Output

Print one integer, the maximum score over all partitions of the sequence into $k$ regions.

Examples2

Example 1
Input
```
5 3
10 5 4 8 3
```
Expected output
```
2
```
Example 2
Input
```
5 3
10 11 12 13 14
```
Expected output
```
0
```