## 1. Abridged problem statement

Given an array `a[1..n]`, where `0 ≤ a[i] < m`, define for every shift value `t = 0, 1, ..., m-1` a new array

\[
b_t[i] = (a[i] + t) \bmod m.
\]

For each `t`, consider all cyclic rotations of `b_t` and choose the lexicographically smallest one. Output the `k`-th element of that smallest cyclic rotation, for every `t = 0..m-1`.

---

## 2. Detailed editorial

### Key observation

For a fixed `t`, every value of the array is transformed as:

\[
a_i \mapsto (a_i + t) \bmod m
\]

As `t` increases, all values increase together modulo `m`. The relative order of values changes only when some value wraps from `m - 1` to `0`.

For an original value `v`, this wrap happens when:

\[
(v + t) \bmod m = 0
\]

so

\[
t = (m - v) \bmod m.
\]

These special times are called **wrap points**.

Between two consecutive wrap points, no value wraps. Therefore, the relative ordering of all values present in the array stays unchanged. That means the lexicographically smallest cyclic shift also stays the same throughout such an interval.

---

### Phases

Let the sorted wrap points be:

```text
w[0] < w[1] < ... < w[cnt - 1]
```

They split the circular interval `[0, m)` into phases:

```text
[w[0], w[1]), [w[1], w[2]), ..., [w[cnt-1], w[0] + m)
```

Inside one phase starting at `L`, the smallest transformed value comes from the original value

\[
v = (m - L) \bmod m.
\]

Indeed, at time `L`, all positions with `a[i] = v` become `0`, which is the smallest possible value.

Therefore, in that phase, the lexicographically smallest rotation must start at some position `i` such that:

```cpp
a[i] == v
```

So for each distinct value `v` appearing in `a`, we need to find the best cyclic rotation starting from one of the positions where `a[i] = v`.

---

### Comparing two cyclic rotations efficiently

Suppose we compare two cyclic rotations starting at positions `p` and `q`, both having `a[p] = a[q] = v`.

At the phase where value `v` is mapped to `0`, comparison is done under the transformed alphabet:

\[
x \mapsto (x - v + m) \bmod m
\]

because value `v` becomes `0`, value `v+1` becomes `1`, and so on.

To compare rotations starting at `p` and `q`:

1. Find their longest common prefix length `l`.
2. If `l >= n`, the rotations are identical.
3. Otherwise compare:

\[
(a[p+l] - v + m) \bmod m
\]

and

\[
(a[q+l] - v + m) \bmod m
\]

The smaller transformed value determines the lexicographically smaller rotation.

---

### How to get longest common prefixes

Cyclic rotations of length `n` can be represented as substrings of length `n` in the doubled array:

```text
a + a
```

For example, the cyclic rotation starting at `p` is:

```text
a[p], a[p+1], ..., a[p+n-1]
```

inside the doubled array.

We build a suffix array on `a + a`.

Using the suffix array and its LCP array, the LCP of suffixes starting at `p` and `q` can be answered by RMQ:

```cpp
LCP(p, q) = min(lcp[rank[p] + 1 ... rank[q]])
```

where `rank[p] < rank[q]`.

We cap the answer by `n`, because cyclic rotations only have length `n`.

---

### Finding the best start for each value

For every value `v`, collect all positions where `a[i] = v`.

Then scan through this group and keep the best start:

```cpp
best = first position with value v

for every other position c with value v:
    compare rotation c with rotation best
    if c is smaller:
        best = c
```

After finding `best`, the `k`-th element of that rotation before applying shift `t` is:

```cpp
base[v] = a[(best + k - 1) % n]
```

For any `t` in the phase belonging to `v`, the required answer is:

```cpp
(base[v] + t) % m
```

---

### Complexity

Let `N = 2n`.

The suffix array implementation uses doubling with `std::sort`, so its complexity is approximately:

\[
O(N \log^2 N)
\]

The remaining work is:

\[
O(n + m)
\]

The RMQ sparse table uses:

\[
O(N \log N)
\]

memory.

---

## 3. 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;
}
```

---

## 4. Python Solution

```python
import sys


def build_suffix_array(s):
    """
    Builds suffix array for a list of integers s using the doubling algorithm.

    sa[i] = starting position of the i-th suffix in sorted order
    rank[pos] = position/rank of suffix starting at pos
    """

    n = len(s)

    # Initially suffixes are identified by their first value.
    sa = list(range(n))
    rank = s[:]

    # Temporary array for updated ranks.
    tmp = [0] * n

    k = 1

    while k < n:
        # Sort suffixes by pair:
        # (rank of first k values, rank of next k values)
        sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))

        # First suffix in sorted order gets rank 0.
        tmp[sa[0]] = 0

        # Assign ranks to all suffixes.
        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
            )

            # Increase rank when key changes.
            tmp[cur] = tmp[prev] + (1 if prev_key != cur_key else 0)

        # Swap rank and tmp.
        rank, tmp = tmp, rank

        # If all suffixes have unique ranks, we are done.
        if rank[sa[-1]] == n - 1:
            break

        # Double compared prefix length.
        k <<= 1

    return sa, rank


def build_lcp(s, sa, rank):
    """
    Kasai algorithm.

    lcp[i] = LCP of suffixes sa[i] and sa[i - 1].
    lcp[0] = 0.
    """

    n = len(s)
    lcp = [0] * n

    h = 0

    for i in range(n):
        r = rank[i]

        if r == 0:
            h = 0
            continue

        # Previous suffix in suffix-array order.
        j = sa[r - 1]

        # Extend while equal.
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1

        lcp[r] = h

        # For next suffix, LCP decreases by at most one.
        if h:
            h -= 1

    return lcp


class SegmentTreeMin:
    """
    Segment tree for range minimum queries.

    It is used instead of a sparse table to keep the Python implementation
    memory-friendly.

    Query range is inclusive: query(l, r).
    """

    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)

        # Put original values at leaves.
        for i, x in enumerate(arr):
            self.tree[self.size + i] = x

        # Build internal nodes.
        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):
        """
        Returns min over inclusive interval [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]

    # Build doubled array so cyclic rotations become ordinary substrings.
    doubled = [a[i % n] for i in range(2 * n)]

    # Build suffix array and rank array.
    sa, rank = build_suffix_array(doubled)

    # Build LCP array.
    lcp = build_lcp(doubled, sa, rank)

    # RMQ over LCP array.
    rmq = SegmentTreeMin(lcp)

    def cyclic_lcp(p, q):
        """
        LCP of cyclic rotations starting at p and q, capped by n.
        """

        if p == q:
            return n

        rp = rank[p]
        rq = rank[q]

        if rp > rq:
            rp, rq = rq, rp

        # LCP of suffixes p and q is min lcp[rp + 1 ... rq].
        return min(n, rmq.query(rp + 1, rq))

    # groups[v] = all positions i where a[i] == v.
    groups = [[] for _ in range(m)]

    for i, x in enumerate(a):
        groups[x].append(i)

    # base[v] stores the original value at the k-th position of the best
    # rotation for the phase where original value v is the smallest.
    base = [0] * m

    # Wrap points caused by values that actually appear.
    wraps = []

    for v in range(m):
        if not groups[v]:
            continue

        # Value v becomes 0 at this shift.
        wraps.append((m - v) % m)

        # Find best cyclic rotation among starts with a[start] == v.
        best = groups[v][0]

        for c in groups[v][1:]:
            l = cyclic_lcp(c, best)

            # Equal rotations.
            if l >= n:
                continue

            # Compare first differing values after relabeling so v becomes 0.
            ca = (a[(c + l) % n] - v) % m
            cb = (a[(best + l) % n] - v) % m

            if ca < cb:
                best = c

        # k-th original value of that best rotation.
        base[v] = a[(best + k - 1) % n]

    # Sort phase starts.
    wraps.sort()

    ans = [0] * m
    w = len(wraps)

    # Fill answers phase by phase.
    for i in range(w):
        L = wraps[i]

        # Circular next wrap.
        R = wraps[i + 1] if i + 1 < w else wraps[0] + m

        # Original value that maps to 0 at L.
        v = (m - L) % m

        # Original k-th value in best rotation.
        bv = base[v]

        # For every t in this phase, answer is shifted by t modulo m.
        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()
```

---

## 5. Compressed editorial

For shift `t`, values become `(a[i] + t) % m`. Their relative order changes only when some value wraps to `0`, i.e. at

\[
t = (m - a[i]) \bmod m.
\]

Sort all such wrap points. Between two consecutive wrap points, the lexicographically smallest cyclic rotation is fixed.

In the phase starting at `L`, the smallest present original value is

\[
v = (m - L) \bmod m.
\]

So the best rotation must start at a position where `a[i] = v`.

For every value `v`, compare all rotations starting at occurrences of `v`. To compare two starts quickly, build a suffix array on `a + a`; then use RMQ over the LCP array to get their common prefix length. The first differing element is compared after relabeling:

\[
x \mapsto (x - v + m) \bmod m.
\]

Once the best start for value `v` is known, store:

```text
base[v] = a[(best + k - 1) % n]
```

Then for every shift `t` in the corresponding phase:

```text
answer[t] = (base[v] + t) % m
```

This gives all `m` answers efficiently.
