<|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++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, k;
vector<int> d;

void read() {
    cin >> n >> k;
    string s;
    cin >> s;

    d.resize(n);
    for(int i = 0; i < n; i++) {
        d[i] = s[i] - '0';
    }
}

template<typename T>
int least_rotation(const vector<T>& s) {
    int n = s.size();
    if(n == 0) {
        return 0;
    }

    vector<int> f(2 * n, -1);
    int k_ = 0;
    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_;
}

template<typename T>
vector<T> max_cyclic_shift(const vector<T>& v) {
    if(v.empty()) {
        return {};
    }

    int m = v.size();
    vector<T> t(m);
    for(int i = 0; i < m; i++) {
        t[i] = -v[i];
    }

    int kk = least_rotation(t);
    vector<T> ans(m);
    for(int i = 0; i < m; ++i) {
        ans[i] = v[(kk + i) % m];
    }

    return ans;
}

void solve() {
    // Following index i by repeated +K mod N visits a cycle of the permutation;
    // the infinite fraction starting at any index of that cycle is periodic with
    // that cycle as its period. Two starts on the same cycle differ only by a
    // rotation of the period, so the largest fraction from a cycle corresponds
    // to its lexicographically maximum cyclic shift (found via Booth's least-
    // rotation algorithm on the negated digits). We take the best shift over all
    // cycles, then print the first N digits by repeating the winning period.

    vector<bool> used(n, false);
    vector<int8_t> ans;
    for(int i = 0; i < n; i++) {
        if(used[i]) {
            continue;
        }

        vector<int8_t> cycle;
        for(int j = i; !used[j]; j = (j + k) % n) {
            used[j] = true;
            cycle.push_back(d[j]);
        }

        cycle = max_cyclic_shift(cycle);
        if(ans.empty() || cycle > ans) {
            ans = cycle;
        }
    }

    for(int i = 0; i < n; i++) {
        cout << (int)ans[i % ans.size()];
    }

    cout << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    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()
```