B :: Circle of digits

Time Limit: 10 Seconds Memory Limit: 131072 KB

You are given a circular string of length N that consists of digits '1'..'9'. You want to split it into K continuous non-empty parts. Each of those parts represents a decimal notation of some integer number. Your goal is to find a partition that minimizes the maximum integer from the partition at hand.

For example, if the string is 7654321 and K=3 then the optimal partition is: {176, 54, 32} which has 176 as the maximum number. Note that the string is cyclic, that is the first character goes right after the last one (as in the 176 part of the above example).

Input

The first line of the input contains two integers N and K (3 ≤ N ≤ 100000, 2 ≤ K ≤ N). The second line contains a string of length N which consists only of characters ‘1’..’9’.

Output

Output the value of the maximal number in the optimal partition.

Sample Input

Sample Output

32
176
3

Submit