0229. Infinite fraction

Input file name:	fraction.in
Output file name:	fraction.out
Time limit:	1 s
Memory limit:	64 megabytes

You are given integer numbers N and K and an array D[0..N-1] of decimal digits (0 ≤ D[i] ≤ 9, D[i] is an integer).

Consider an array A of real numbers, such that integer part of A[i] is equal to zero, and fractional part is an infinite decimal fraction with digits D[(i + 0K) mod N], D[(i + 1K) mod N], D[(i + 2K) mod N] and so on.

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

A[1] = 0.1491491491...
A[2] = 0.9149149149...
A[3] = 0.4914914914...

You are to find an element of array A with the greatest value and output first N digits of its fractional part.

Input file

The first line contains integer numbers N and K (1 ≤ N ≤ 150000; 0 ≤ K ≤ 10⁹). The second line contains an array of digits D, given without spaces.

Output file

You are to output exactly N characters to the output file, according to the task.

Examples:

fraction.in	fraction.out
3 2 194	914
2 1 57	75
4 1 0000	0000

Source: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Discuss       Submit a solution



Printable version