**Note: The time limit for this problem is 4s, 2x the default.**
To celebrate the start of spring, Farmer John's N cows (1≤N≤2⋅105 ) 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=A1<A2<…<AK<N that are "active", meaning the cows in these positions are the next to move (1≤K≤N).
In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position A1 moves to position A2, the cow at position A2 moves to position A3, and so on, with the cow at position AK moving to position A1. 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: A1 becomes A1+1,A2 becomes A2+1, and so on (if Ai =N−1 for some active position, then Ai circles back around to 0).
Please calculate the order of the cows after T minutes of the dance (1≤T≤109).
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains three integers N, K, and T.
The second line contains K integers representing the initial set of active positionsA1,A2,…AK. Recall that A1=0 and that these are given in increasing order.
OUTPUT FORMAT (print output to the terminal / stdout):
Output the order of the cows after T minutes, starting with the cow in position 0, separated by spaces.
SAMPLE INPUT:
5 3 4
0 2 3
SAMPLE OUTPUT:
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]
SCORING:
Inputs 2-7: N≤1000,T≤10000
Inputs 8-13: No additional constraints.
Problem credits: Claire Zhang