<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

232. Infinite Fraction
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



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
The first line contains integer numbers N and K (1<=N<=150000; 0<=K<=10^9). The second line contains an array of digits D, given without spaces.

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

Sample test(s)

Input
Test #1
3 2
194

Test #2
2 1
57

Test #3
4 1
0000

Output
Test #1
914

Test #2
75

Test #3
0000

<|response|>
1. Abridged Problem Statement  
You have N digits D[0..N−1] arranged in a circle. For each start index i (0≤i<N), define an infinite fractional number  
  A[i] = 0.( D[i], D[(i+K)%N], D[(i+2K)%N], … )  
Since all A[i] lie in [0,1), “greater value” means lexicographically larger infinite digit sequence. Find the i that maximizes A[i] and output the first N digits of its fractional part.

2. Key Observations  
- Stepping by K modulo N partitions the set {0,…,N−1} into disjoint cycles.  
- If a cycle has length L, then the digit sequence for any start in that cycle is just a cyclic rotation of the same block of L digits, repeated infinitely.  
- Comparing two infinite decimals boils down to lexicographically comparing their infinite digit sequences.  
- Within one cycle, the maximum infinite decimal is achieved by choosing the lexicographically largest cyclic rotation of the block.  
- We must compute that best rotation for every cycle and then pick the overall best.  
- Booth’s algorithm finds the lexicographically minimal rotation of a string in O(L). To get the maximal rotation, we can negate (or invert) comparisons.

3. Full Solution Approach  
a. Read N, K and the digit array D[0..N−1].  
b. Prepare an array used[0..N−1]=false, and a container bestBlock to hold the digits of the globally best cycle’s optimal rotation.  
c. For each index i from 0 to N−1, if used[i] is false:  
   1. Follow the cycle starting at i by repeatedly doing j ← (j+K)%N until you return to a visited index, collecting the digits D[j] into a vector cycleDigits and marking used[j]=true. Let L = cycleDigits.size().  
   2. Compute the lexicographically largest rotation of cycleDigits using a modified Booth’s algorithm (O(L)). Call the result rotated.  
   3. If rotated > bestBlock lexicographically, update bestBlock = rotated.  
d. Now bestBlock has length L_best. The answer is the first N digits of the infinite repetition of bestBlock: for t=0..N−1, output bestBlock[t % L_best] without separators.  

Total time is O(N) since every index is visited once and each cycle of length L is processed in O(L).

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

// Booth’s algorithm: find start of lexicographically minimal rotation of s in O(n)
int least_rotation(const vector<int>& s) {
    int n = s.size();
    if (n == 0) return 0;
    vector<int> f(2*n, -1);
    int k = 0;  // candidate start
    for (int j = 1; j < 2*n; ++j) {
        int i = f[j - k - 1];
        while (i != -1 && s[j % n] != s[(k + i + 1) % n]) {
            if (s[j % n] < s[(k + i + 1) % n]) {
                k = j - i - 1;
            }
            i = f[i];
        }
        if (i == -1 && s[j % n] != s[(k + i + 1) % n]) {
            if (s[j % n] < s[(k + i + 1) % n]) {
                k = j;
            }
            f[j - k] = -1;
        } else {
            f[j - k] = i + 1;
        }
    }
    return k;
}

// Return the lexicographically maximal cyclic rotation of v
vector<int> max_cyclic_shift(const vector<int>& v) {
    int n = v.size();
    if (n == 0) return {};
    // Negate digits so that minimal rotation of negated corresponds to maximal of original
    vector<int> neg(n);
    for (int i = 0; i < n; ++i) neg[i] = -v[i];
    int start = least_rotation(neg);
    vector<int> res(n);
    for (int i = 0; i < n; ++i) {
        res[i] = v[(start + i) % n];
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;
    string s;
    cin >> s;

    // Read digit array
    vector<int> D(N);
    for (int i = 0; i < N; ++i) {
        D[i] = s[i] - '0';
    }

    vector<bool> used(N, false);
    vector<int> bestBlock;

    // Process each cycle
    for (int i = 0; i < N; ++i) {
        if (used[i]) continue;
        vector<int> cycleDigits;
        int j = i;
        // Collect the cycle
        while (!used[j]) {
            used[j] = true;
            cycleDigits.push_back(D[j]);
            j = (j + K) % N;
        }
        // Find its best cyclic rotation
        vector<int> candidate = max_cyclic_shift(cycleDigits);
        // Keep the best among all cycles
        if (bestBlock.empty() || candidate > bestBlock) {
            bestBlock = move(candidate);
        }
    }

    // Output the first N digits of the infinite repetition of bestBlock
    int L = bestBlock.size();
    for (int t = 0; t < N; ++t) {
        cout << bestBlock[t % L];
    }
    cout << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
sys.setrecursionlimit(10**7)

def least_rotation(s):
    """
    Booth’s algorithm to find the index of the
    lexicographically minimal rotation of list s.
    Time: O(len(s))
    """
    n = len(s)
    if n == 0:
        return 0
    # failure function for “window matching” over s+s
    f = [-1] * (2*n)
    k = 0  # candidate start
    for j in range(1, 2*n):
        i = f[j - k - 1]
        while i != -1 and s[j % n] != s[(k + i + 1) % n]:
            if s[j % n] < s[(k + i + 1) % n]:
                k = j - i - 1
            i = f[i]
        if i == -1 and s[j % n] != s[(k + i + 1) % n]:
            if s[j % n] < s[(k + i + 1) % n]:
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k

def max_cyclic_shift(v):
    """
    Return the lexicographically maximal cyclic rotation of list v.
    We invert the values and find the minimal rotation on the negated list.
    """
    if not v:
        return []
    neg = [-x for x in v]
    start = least_rotation(neg)
    n = len(v)
    # build the rotated block
    return [v[(start + i) % n] for i in range(n)]

def main():
    data = sys.stdin.read().split()
    N, K = map(int, data[:2])
    s = data[2].strip()
    D = [int(ch) for ch in s]

    used = [False] * N
    best_block = None

    # Decompose into cycles and process each
    for i in range(N):
        if used[i]:
            continue
        cycle = []
        j = i
        while not used[j]:
            used[j] = True
            cycle.append(D[j])
            j = (j + K) % N
        # get the maximal rotation for this cycle
        candidate = max_cyclic_shift(cycle)
        if best_block is None or candidate > best_block:
            best_block = candidate

    # Output first N digits of infinite repetition of best_block
    L = len(best_block)
    answer = ''.join(str(best_block[i % L]) for i in range(N))
    print(answer)

if __name__ == "__main__":
    main()
```