<|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.

426. Double cyclic
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Consider a sequence of numbers a1, a2,..., an. Its cyclic shift is any sequence obtained from it by taking some (possibly none) of its starting elements and moving them to the end in the same order. In other words, it is a sequence ak, ak+1,..., an-1, an, a1, a2,..., ak-2, ak-1 for some k.

The smallest cyclic shift of a given sequence is its cyclic shift that is smallest lexicographically. A sequence is lexicographically smaller than another sequence of the same length if and only if it has a smaller number in the first position they differ.

Now, consider a sequence  of integers a1, a2,..., an where  0 ≤ ai ≤ m-1, where m is some fixed constant. We define  to be the sequence .

Given , m and an integer k between 1 and n, output m integer numbers: the k-th element of the smallest cyclic shift of , the k-th element of the smallest cyclic shift of ,..., the k-th element of the smallest cyclic shift of .

Input
The first line of the input file contains three integers n, m and k (, 1 ≤ k ≤ n). The second line of the input line contains n integers a1, a2,..., an (0 ≤ ai ≤ m-1).

Output
Output m integer numbers one per line — k-th elements of the smallest cyclic shifts of the sequences explained above.

Example(s)
sample input
sample output
5 6 3
1 2 1 2 3
1
2
3
5
5
0

<|response|>
## 1. Abridged problem statement

We are given an array `a[1..n]`, where `0 ≤ a[i] < m`. For every shift value `t = 0, 1, ..., m-1`, define a new array `b_t[i] = (a[i] + t) mod m`. For each `b_t`, consider all of its cyclic rotations and choose the lexicographically smallest one. For every `t`, output the `k`-th element of the lexicographically smallest cyclic rotation of `b_t`.

---

## 2. Key observations

### Observation 1: The order only changes when some value wraps to `0`

As `t` increases, all values increase together modulo `m`. The relative order between values changes only when some value wraps from `m - 1` to `0`. For an original value `v`, this happens at `t = (m - v) mod m`. These values of `t` are called **wrap points**.

### Observation 2: Between two consecutive wrap points, the answer structure is fixed

Sorting all wrap points caused by values that actually appear in the array, between two consecutive wrap points no present value wraps. The relative order of all values remains unchanged, so the lexicographically smallest cyclic rotation starts at the same position throughout that whole interval. This splits all shifts into phases.

### Observation 3: In a phase, the best rotation must start with the current smallest value

In a phase starting at shift `L`, some original value `v = (m - L) mod m` becomes `0`. Since `0` is the smallest possible value, the lexicographically smallest rotation must start at a position `i` where `a[i] == v`. For each distinct value `v`, we need to find the best cyclic rotation among all positions where `a[i] = v`.

### Observation 4: Comparing two cyclic rotations can be done using LCP

Cyclic rotations of length `n` are substrings of length `n` in the doubled array `a + a`. We build a suffix array over the doubled array; with suffix array + LCP RMQ we find the longest common prefix of the rotations at `p` and `q` in O(1). The first differing element is compared as `(a[p + len] - v + m) mod m` vs `(a[q + len] - v + m) mod m`.

---

## 3. Full solution approach

Build a suffix array and LCP array on the doubled array `a + a`, plus a sparse-table RMQ over the LCP array. For every distinct value `v` that appears in `a`, collect all positions where `a[i] = v`, find the best cyclic rotation among them (comparing via LCP + transformed comparison), and store `base[v] = a[(best + k - 1) % n]`. Collect wrap points `(m - v) % m` for each occurring `v`, sort them, and fill the answer array phase by phase: for a phase starting at `L` with `v = (m - L) % m`, every `t` in `[L, R)` gets answer `(base[v] + t) % m`. Overall O(n log n + m).

---

## 4. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/data_structures/sparse_table.hpp>
// #include <coding_library/strings/suffix_array.hpp>

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;
};

template<class T, T (*merge)(T, T)>
class SparseTable {
  private:
    int n;
    vector<vector<T>> dp;
    vector<int> prec_lg2;

  public:
    SparseTable() {
        n = 0;
        dp.clear();
        prec_lg2.clear();
    }

    void init(const vector<T>& a) {
        n = a.size();
        prec_lg2.resize(n + 1);
        for(int i = 2; i <= n; i++) {
            prec_lg2[i] = prec_lg2[i >> 1] + 1;
        }

        dp.assign(prec_lg2[n] + 1, vector<T>(n));
        dp[0] = a;

        for(int j = 1; (1 << j) <= n; j++) {
            for(int i = 0; i + (1 << j) <= n; i++) {
                dp[j][i] = merge(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    T query(int l, int r) {
        int k = prec_lg2[r - l + 1];
        return merge(dp[k][l], dp[k][r - (1 << k) + 1]);
    }
};

template<class T = string>
class SuffixArray {
  private:
    using G = conditional_t<
        is_same_v<T, const char*> || is_same_v<T, char*> || is_array_v<T>, char,
        typename T::value_type>;

    void build_sa(const T& s) {
        sa.resize(n);
        rnk.resize(n);
        vector<int> tmp(n);

        for(int i = 0; i < n; i++) {
            sa[i] = i;
            rnk[i] = (int)s[i];
        }

        for(int k = 1; k < n; k <<= 1) {
            auto cmp = [&](int x, int y) {
                if(rnk[x] != rnk[y]) {
                    return rnk[x] < rnk[y];
                }
                int rx = x + k < n ? rnk[x + k] : -1;
                int ry = y + k < n ? rnk[y + k] : -1;
                return rx < ry;
            };

            sort(sa.begin(), sa.end(), cmp);
            tmp[sa[0]] = 0;
            for(int i = 1; i < n; i++) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
            }

            rnk = tmp;
            if(rnk[sa[n - 1]] == n - 1) {
                break;
            }
        }
    }

    void build_lcp(const T& s) {
        lcp.assign(n, 0);
        int h = 0;
        for(int i = 0; i < n; i++) {
            if(rnk[i] > 0) {
                int j = sa[rnk[i] - 1];
                while(i + h < n && j + h < n && s[i + h] == s[j + h]) {
                    h++;
                }

                lcp[rnk[i]] = h;
                if(h > 0) {
                    h--;
                }
            } else {
                h = 0;
            }
        }
    }

  public:
    int n;
    vector<int> sa, rnk, lcp;

    SuffixArray() : n(0) {}
    SuffixArray(const T& s) { init(s); }

    void clear() {
        n = 0;
        sa.clear();
        rnk.clear();
        lcp.clear();
    }

    void init(const T& s) {
        clear();
        n = (int)size(s);
        if(n == 0) {
            return;
        }

        build_sa(s);
        build_lcp(s);
    }
};

int min_custom(int a, int b) { return min(a, b); }

int n, m, k;
vector<int> a;

void read() {
    cin >> n >> m >> k;
    a.resize(n);
    cin >> a;
}

void solve() {
    // For each shift t we want the k-th element of the lex smallest cyclic
    // rotation of b_i(t) = (a_i + t) mod m. As t grows every b_i grows by 1
    // too, except whenever some b_i wraps from m-1 to 0. The wrap points are
    // t = (m - v) mod m for each distinct v in a, and sorted they split
    // [0, m) into phases.
    //
    // Inside a phase [L, R) nothing wraps, so every b_i moves in lockstep and
    // all pairwise inequalities among the b values are preserved. The lcp
    // lengths between any two rotations only see equalities in a so they
    // don't depend on t at all, and the tie-breaking character that picked
    // the optimal start at t = L stays the same. So the optimal start is
    // constant over the phase. The converse is also clear: for another
    // position to overtake the current best inside the phase it would have
    // to become 0 first (a 0 in the first position beats any non-zero
    // start), but that would make that t a wrap point and not interior to
    // the phase. So inside [L, R) we can fixate on a single starting index.
    //
    // For the phase of v = (m - L) mod m the rotations whose first b value
    // is 0 are exactly the ones starting at positions where a_i = v, so the
    // best start lives in C_v = { i : a_i = v }. To pick between two starts
    // in C_v in O(1) we build a suffix array + lcp on the doubled array
    // a + a and an RMQ over the lcp; the tie-breaking character is read as
    // (a[...] - v) mod m so the comparison matches the actual b(t) order.
    //
    // Once s_v is known, every t in the phase of v has answer
    // (a[(s_v + k - 1) mod n] + t) mod m, so we just walk the phase and write
    // the values out one by one. Overall O(n log n + m).

    vector<int> doubled(2 * n);
    for(int i = 0; i < 2 * n; i++) {
        doubled[i] = a[i % n];
    }

    SuffixArray<vector<int>> sa;
    sa.init(doubled);

    SparseTable<int, min_custom> rmq;
    rmq.init(sa.lcp);

    auto cyclic_lcp = [&](int p, int q) {
        if(p == q) {
            return n;
        }

        int rp = sa.rnk[p], rq = sa.rnk[q];
        if(rp > rq) {
            swap(rp, rq);
        }

        return min(n, rmq.query(rp + 1, rq));
    };

    vector<vector<int>> groups(m);
    for(int i = 0; i < n; i++) {
        groups[a[i]].push_back(i);
    }

    vector<int> base(m, 0);
    vector<int> wraps;
    wraps.reserve(min(n, m));

    for(int v = 0; v < m; v++) {
        if(groups[v].empty()) {
            continue;
        }

        wraps.push_back((m - v) % m);

        int best = groups[v][0];
        for(int idx = 1; idx < (int)groups[v].size(); idx++) {
            int c = groups[v][idx];
            int l = cyclic_lcp(c, best);
            if(l >= n) {
                continue;
            }

            int ca = (a[(c + l) % n] - v + m) % m;
            int cb = (a[(best + l) % n] - v + m) % m;
            if(ca < cb) {
                best = c;
            }
        }

        base[v] = a[(best + k - 1) % n];
    }

    sort(wraps.begin(), wraps.end());

    vector<int> ans(m);
    int w = (int)wraps.size();
    for(int i = 0; i < w; i++) {
        int L = wraps[i];
        int R = (i + 1 < w) ? wraps[i + 1] : wraps[0] + m;
        int v = (m - L) % m;
        int bv = base[v];
        for(int t = L; t < R; t++) {
            int tt = t % m;
            ans[tt] = (bv + tt) % m;
        }
    }

    for(int t = 0; t < m; t++) {
        cout << ans[t] << '\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();
        solve();
    }

    return 0;
}
```

---

## 5. Python Solution

```python
import sys


def build_suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rank = s[:]
    tmp = [0] * n
    k = 1
    while k < n:
        sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
        tmp[sa[0]] = 0
        for i in range(1, n):
            prev = sa[i - 1]
            cur = sa[i]
            prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1)
            cur_key = (rank[cur], rank[cur + k] if cur + k < n else -1)
            tmp[cur] = tmp[prev] + (1 if prev_key != cur_key else 0)
        rank, tmp = tmp, rank
        if rank[sa[-1]] == n - 1:
            break
        k <<= 1
    return sa, rank


def build_lcp(s, sa, rank):
    n = len(s)
    lcp = [0] * n
    h = 0
    for i in range(n):
        r = rank[i]
        if r == 0:
            h = 0
            continue
        j = sa[r - 1]
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1
        lcp[r] = h
        if h:
            h -= 1
    return lcp


class SegmentTreeMin:
    def __init__(self, arr):
        n = len(arr)
        self.size = 1
        while self.size < n:
            self.size <<= 1
        self.inf = 10 ** 18
        self.tree = [self.inf] * (2 * self.size)
        for i, x in enumerate(arr):
            self.tree[self.size + i] = x
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = min(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        l += self.size
        r += self.size
        ans = self.inf
        while l <= r:
            if l & 1:
                ans = min(ans, self.tree[l])
                l += 1
            if not (r & 1):
                ans = min(ans, self.tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return ans


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m, k = data[0], data[1], data[2]
    a = data[3:3 + n]
    doubled = [a[i % n] for i in range(2 * n)]
    sa, rank = build_suffix_array(doubled)
    lcp = build_lcp(doubled, sa, rank)
    rmq = SegmentTreeMin(lcp)

    def cyclic_lcp(p, q):
        if p == q:
            return n
        rp, rq = rank[p], rank[q]
        if rp > rq:
            rp, rq = rq, rp
        return min(n, rmq.query(rp + 1, rq))

    groups = [[] for _ in range(m)]
    for i, x in enumerate(a):
        groups[x].append(i)

    base = [0] * m
    wraps = []
    for v in range(m):
        if not groups[v]:
            continue
        wraps.append((m - v) % m)
        best = groups[v][0]
        for c in groups[v][1:]:
            l = cyclic_lcp(c, best)
            if l >= n:
                continue
            ca = (a[(c + l) % n] - v) % m
            cb = (a[(best + l) % n] - v) % m
            if ca < cb:
                best = c
        base[v] = a[(best + k - 1) % n]

    wraps.sort()
    ans = [0] * m
    w = len(wraps)
    for i in range(w):
        L = wraps[i]
        R = wraps[i + 1] if i + 1 < w else wraps[0] + m
        v = (m - L) % m
        bv = base[v]
        for t in range(L, R):
            tt = t % m
            ans[tt] = (bv + tt) % m

    sys.stdout.write("\n".join(map(str, ans)))


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