Infinite fraction#2075

Infinite fraction

2 seconds
64 megabytes
Easy

You are given two numbers, and , along with an array D[0..N-1] consisting of decimal digits (0 \le D[i] \le 9), where each is an integer.

Consider an array of real numbers. Each has an integer part equal to zero, and its fractional part is an infinite decimal sequence formed by the digits D[(i+0K) \bmod N], D[(i+1K) \bmod N], D[(i+2K) \bmod N], and so on.

For example, if N = 3, K = 2, D = '194':

A[1] = 0.149149149\ldots A[2] = 0.914914914\ldots A[3] = 0.491491491\ldots

You are required to determine the element in the array with the largest value and output the first digits of its fractional part.

Input

The first line contains the numbers and (1 \le N \le 150\ 000, 0 \le K \le 10^9). The second line contains the array .

Output

Print the first digits of the fractional part of the maximum element of array .

Examples

Example 1

Loading
Loading