题目描述

Note: The time limit for this problem is 4s, 2x the default.

To celebrate the start of spring, Farmer John's $N$ cows have invented an intriguing new dance, where they stand in a circle and re-order themselves in a predictable way.

Specifically, there are $N$ positions around the circle, numbered sequentially from $0$ to $N-1$, with position $0$ following position $N-1$. A cow resides at each position. The cows are also numbered sequentially from $0$ to $N-1$. Initially, cow $i$ starts in position $i$. You are told a set of $K$ positions $0=A_1<A_2<\dots<A_K<N$ that are "active", meaning the cows in these positions are the next to move.

In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position $A_1$ moves to position $A_2$, the cow at position $A_2$ moves to position $A_3$, and so on, with the cow at position $A_K$ moving to position $A_1$. All of these $K$ moves happen simultaneously, so the after the rotation is complete, all of the active positions still contain exactly one cow. Next, the active positions themselves shift: $A_1$ becomes $A_1+1$, $A_2$ becomes $A_2+1$, and so on (if $A_i = N-1$ for some active position, then $A_i$ circles back around to $0$).

Please calculate the order of the cows after $T$ minutes of the dance.

输入格式

The first line contains three integers $N, K$ and $T$.

The second line contains $K$ integers representing the initial set of active positions $A_1,A_2, \dots, A_K$. Recall that $A_1 = 0$ and that these are given in increasing order.

输出格式

Output the order of the cows after $T$ minutes, starting with the cow in position $0$, separated by spaces.

题目大意

为了庆祝春天的开始，FJ 的 $N$ 头奶牛发明了一个有趣的新舞蹈。在这个舞蹈中，他们站成一个圆圈，并以一种给定的方式移动。

具体地，圆圈上有 $N$ 个位置，按顺序分别编号为 $0$ 至 $N - 1$，其中位置 $N - 1$ 之后是位置 $0$。每个位置都有恰好一头奶牛。奶牛也按顺序分别编号为 $0$ 至 $N - 1$。初始状态中，编号为 $i$ 的奶牛位于编号为 $i$ 的位置。在圆圈上，有 $K$ 个活跃位置 $0 = A_1 < A_2 < \dots < A_K < N$，在活跃位置上的奶牛将会移动。

在舞蹈的每一分钟里，都会发生两件事。首先，在活跃位置上的奶牛会发生轮换：在 $A_1$ 位置的奶牛移到 $A_2$ 位置，在 $A_2$ 位置的奶牛移到 $A_3$ 位置……在 $A_K$ 位置的奶牛移到 $A_1$ 位置。所有 $K$ 个移动同时发生，因此，在轮换结束后，每个活跃位置上仍有恰好一头奶牛。接下来，活跃位置会发生变换：$A_1$ 变为 $A_1 + 1$，$A_2$ 变为 $A_2 + 1$，以此类推（若某个活跃位置满足 $A_i = N - 1$，则 $A_i$ 变为 $0$）。

请求出舞蹈持续 $T$ 分钟后奶牛的顺序。

5 3 4
0 2 3

1 2 3 4 0

提示

For the example above, here are the cow orders and $A$ for the first four timesteps:

Initial, T = 0: order = [0 1 2 3 4], A = [0 2 3]
T = 1: order = [3 1 0 2 4]
T = 1: A = [1 3 4]
T = 2: order = [3 4 0 1 2]
T = 2: A = [2 4 0]
T = 3: order = [2 4 3 1 0]
T = 3: A = [3 0 1]
T = 4: order = [1 2 3 4 0]

$1 \leq K \leq N \leq 2 \cdot 10^5$, $1\le T\le 10^9$.

• Inputs 2-7: $N \leq 1000, T \leq 10000$.
• Inputs 8-13: No additional constraints.