<|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, a_2, \dots, a_n
\]

where:

\[
0 \le a_i < m
\]

For every shift value:

\[
t = 0, 1, \dots, m - 1
\]

define a new array:

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

For each array `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 needed to solve the problem

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

For a fixed shift `t`, every value becomes:

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

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 when:

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

So:

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

These values of `t` are called **wrap points**.

---

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

Suppose we sort all wrap points caused by values that actually appear in the array.

Between two consecutive wrap points, no present value wraps around. Therefore, the relative order of all values remains unchanged.

That means the lexicographically smallest cyclic rotation starts at the same position throughout that whole interval.

So we can split all shifts `t = 0..m-1` into phases.

---

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

Consider a phase starting at shift `L`.

At this shift, some original value:

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

becomes `0`.

Since `0` is the smallest possible value, the lexicographically smallest rotation must start at a position `i` where:

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

So for every 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

Suppose two candidate rotations start at positions `p` and `q`, and:

```cpp
a[p] == a[q] == v
```

To compare them, we need to know where they first differ.

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

```text
a + a
```

So we build a suffix array over the doubled array.

With suffix array + LCP RMQ, we can find the longest common prefix of the rotations starting at `p` and `q` in `O(1)` or `O(log n)` time.

If the first differing position is at offset `len`, we compare:

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

and

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

This corresponds to comparing values under the order where original value `v` becomes `0`.

---

## 3. Full solution approach based on the observations

### Step 1: Build doubled array

Create:

```cpp
doubled = a + a
```

Every cyclic rotation of `a` starting at position `i` is a length-`n` substring of `doubled` starting at `i`.

---

### Step 2: Build suffix array and LCP RMQ

Build a suffix array over `doubled`.

Also build the LCP array, where:

```text
lcp[i] = LCP of suffixes sa[i] and sa[i - 1]
```

Using RMQ over the LCP array, we can answer:

```cpp
LCP(rotation starting at p, rotation starting at q)
```

efficiently.

The result is capped by `n`, because rotations have length `n`.

---

### Step 3: Group positions by value

For each value `v`, store all indices where:

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

Only values that appear in the array matter.

---

### Step 4: Find the best start for each value

For every value `v` that appears:

1. Let `positions = all i such that a[i] == v`.
2. Start with `best = positions[0]`.
3. Compare every other candidate start with `best`.
4. Keep the lexicographically smallest cyclic rotation under the transformed order where `v` is treated as `0`.

After finding the best start for value `v`, store:

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

This is the original value at the `k`-th position of the best rotation for the phase where `v` is the smallest value.

---

### Step 5: Fill answers phase by phase

For every appearing value `v`, its wrap point is:

```cpp
wrap = (m - v) % m
```

Sort all wrap points.

Each adjacent pair of wrap points forms a phase.

For a phase starting at `L`:

```cpp
v = (m - L) % m
```

The answer for every shift `t` in this phase is:

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

Finally print:

```cpp
answer[0], answer[1], ..., answer[m - 1]
```

---

### Complexity

Let:

\[
N = 2n
\]

Suffix array with doubling and sorting:

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

or practically:

\[
O(N \log N)
\]

comparisons of integer pairs.

Finding all best rotations:

\[
O(n)
\]

RMQ queries are efficient.

Filling answers:

\[
O(m)
\]

Total complexity:

\[
O(n \log^2 n + m)
\]

Memory:

\[
O(n \log n + m)
\]

for the sparse table version.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
    Sparse table for range minimum query.

    We use it on the LCP array.
    query(l, r) returns min(lcp[l..r]).
*/
class SparseTable {
private:
    int n;
    vector<vector<int>> table;
    vector<int> lg;

public:
    SparseTable() {}

    SparseTable(const vector<int>& arr) {
        build(arr);
    }

    void build(const vector<int>& arr) {
        n = (int)arr.size();

        lg.assign(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i / 2] + 1;
        }

        int levels = lg[n] + 1;
        table.assign(levels, vector<int>(n));

        table[0] = arr;

        for (int j = 1; j < levels; j++) {
            int len = 1 << j;
            int half = len >> 1;

            for (int i = 0; i + len <= n; i++) {
                table[j][i] = min(table[j - 1][i],
                                  table[j - 1][i + half]);
            }
        }
    }

    int query(int l, int r) const {
        int len = r - l + 1;
        int j = lg[len];

        return min(table[j][l],
                   table[j][r - (1 << j) + 1]);
    }
};

/*
    Suffix array for vector<int>.

    sa[i] = starting index of the i-th smallest suffix.
    rank[pos] = position of suffix pos in suffix array.
    lcp[i] = LCP(sa[i], sa[i - 1]).
*/
class SuffixArray {
public:
    int n;
    vector<int> sa;
    vector<int> rank;
    vector<int> lcp;

    SuffixArray() {}

    SuffixArray(const vector<int>& s) {
        build(s);
    }

    void build(const vector<int>& s) {
        n = (int)s.size();

        sa.resize(n);
        rank.resize(n);

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

        vector<int> tmp(n);

        /*
            Doubling algorithm.

            At step len, suffixes are sorted by:
            1. rank of first len elements
            2. rank of next len elements
        */
        for (int len = 1; len < n; len <<= 1) {
            auto cmp = [&](int x, int y) {
                if (rank[x] != rank[y]) {
                    return rank[x] < rank[y];
                }

                int rx = x + len < n ? rank[x + len] : -1;
                int ry = y + len < n ? rank[y + len] : -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);
            }

            rank = tmp;

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

        build_lcp(s);
    }

private:
    void build_lcp(const vector<int>& s) {
        lcp.assign(n, 0);

        int h = 0;

        /*
            Kasai algorithm.

            For each suffix starting at i, compare it with the previous suffix
            in suffix array order.
        */
        for (int i = 0; i < n; i++) {
            int r = rank[i];

            if (r == 0) {
                h = 0;
                continue;
            }

            int j = sa[r - 1];

            while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
                h++;
            }

            lcp[r] = h;

            if (h > 0) {
                h--;
            }
        }
    }
};

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

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    /*
        Build doubled array.

        A cyclic rotation starting at i is represented by:
        doubled[i], doubled[i + 1], ..., doubled[i + n - 1]
    */
    vector<int> doubled(2 * n);

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

    /*
        Suffix array and LCP RMQ on doubled array.
    */
    SuffixArray suffixArray(doubled);
    SparseTable rmq(suffixArray.lcp);

    /*
        Returns LCP of cyclic rotations starting at p and q,
        capped by n.
    */
    auto cyclic_lcp = [&](int p, int q) {
        if (p == q) {
            return n;
        }

        int rp = suffixArray.rank[p];
        int rq = suffixArray.rank[q];

        if (rp > rq) {
            swap(rp, rq);
        }

        /*
            LCP of suffixes p and q is:
            min(lcp[rp + 1], ..., lcp[rq])
        */
        return min(n, rmq.query(rp + 1, rq));
    };

    /*
        Group all positions by their value.
    */
    vector<vector<int>> positions(m);

    for (int i = 0; i < n; i++) {
        positions[a[i]].push_back(i);
    }

    /*
        base[v] stores the original value at the k-th position of the best
        rotation in the phase where original value v becomes the smallest.
    */
    vector<int> base(m, 0);

    /*
        Wrap points caused by values that actually appear.
    */
    vector<int> wraps;

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

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

        /*
            Find best cyclic rotation among all positions where a[pos] == v.
        */
        int best = positions[v][0];

        for (int idx = 1; idx < (int)positions[v].size(); idx++) {
            int candidate = positions[v][idx];

            int common = cyclic_lcp(candidate, best);

            /*
                If common >= n, the two cyclic rotations are identical.
            */
            if (common >= n) {
                continue;
            }

            /*
                Compare first differing element under order where v becomes 0.

                transformed(x) = (x - v + m) % m
            */
            int candidateValue =
                (a[(candidate + common) % n] - v + m) % m;

            int bestValue =
                (a[(best + common) % n] - v + m) % m;

            if (candidateValue < bestValue) {
                best = candidate;
            }
        }

        /*
            Store original k-th value of this best rotation.
        */
        base[v] = a[(best + k - 1) % n];
    }

    /*
        Sort wrap points to get phases.
    */
    sort(wraps.begin(), wraps.end());

    vector<int> answer(m);

    int w = (int)wraps.size();

    /*
        Fill answers phase by phase.
    */
    for (int i = 0; i < w; i++) {
        int L = wraps[i];
        int R = (i + 1 < w) ? wraps[i + 1] : wraps[0] + m;

        /*
            Original value that maps to 0 at shift L.
        */
        int v = (m - L) % m;

        int kthOriginalValue = base[v];

        for (int t = L; t < R; t++) {
            int shift = t % m;
            answer[shift] = (kthOriginalValue + shift) % m;
        }
    }

    for (int t = 0; t < m; t++) {
        cout << answer[t] << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


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

    sa[i] = starting index of the i-th smallest suffix.
    rank[pos] = rank of suffix starting at pos.
    """

    n = len(s)

    sa = list(range(n))
    rank = s[:]
    tmp = [0] * n

    length = 1

    while length < n:
        """
        Sort suffixes by:
        1. rank[i]
        2. rank[i + length]
        """
        sa.sort(
            key=lambda i: (
                rank[i],
                rank[i + length] if i + length < 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 + length] if prev + length < n else -1
            )

            cur_key = (
                rank[cur],
                rank[cur + length] if cur + length < 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

        length <<= 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

        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 > 0:
            h -= 1

    return lcp


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

    It is used on the LCP array.

    query(l, r) returns min over lcp[l..r], inclusive.
    """

    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, value in enumerate(arr):
            self.tree[self.size + i] = value

        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):
        result = self.inf

        l += self.size
        r += self.size

        while l <= r:
            if l & 1:
                result = min(result, self.tree[l])
                l += 1

            if not (r & 1):
                result = min(result, self.tree[r])
                r -= 1

            l >>= 1
            r >>= 1

        return result


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.

    A cyclic rotation starting at i is represented by:
    doubled[i], doubled[i + 1], ..., doubled[i + n - 1]
    """
    doubled = [a[i % n] for i in range(2 * n)]

    """
    Build suffix array and LCP.
    """
    sa, rank = build_suffix_array(doubled)
    lcp = build_lcp(doubled, sa, rank)

    rmq = SegmentTreeMin(lcp)

    def cyclic_lcp(p, q):
        """
        Returns 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

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

    """
    Group all positions by value.
    """
    positions = [[] for _ in range(m)]

    for i, value in enumerate(a):
        positions[value].append(i)

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

    """
    Wrap points caused by values that appear in the array.
    """
    wraps = []

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

        wraps.append((m - v) % m)

        """
        Find best cyclic rotation among starts where a[start] == v.
        """
        best = positions[v][0]

        for candidate in positions[v][1:]:
            common = cyclic_lcp(candidate, best)

            if common >= n:
                continue

            """
            Compare first differing values under transformed order:

            transformed(x) = (x - v) mod m
            """
            candidate_value = (a[(candidate + common) % n] - v) % m
            best_value = (a[(best + common) % n] - v) % m

            if candidate_value < best_value:
                best = candidate

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

    """
    Sort wrap points to define phases.
    """
    wraps.sort()

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

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

        if i + 1 < w:
            R = wraps[i + 1]
        else:
            R = wraps[0] + m

        """
        Original value that becomes 0 at shift L.
        """
        v = (m - L) % m

        kth_original_value = base[v]

        for t in range(L, R):
            shift = t % m
            answer[shift] = (kth_original_value + shift) % m

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


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

The C++ version is the intended efficient implementation. The Python version follows the same logic and is mainly useful for clarity or environments with relaxed limits.