Problem Description

Do you know the traditional Japanese lottery, Amida-kuji?

When conducting an Amida-kuji, first draw \( N \) parallel vertical lines. Then, draw \( M \) horizontal lines within them. Each horizontal line must connect two adjacent vertical lines, and no two horizontal lines can be at the same height. Let's say the \( i \)-th (\( 1 \leq i \leq M \)) horizontal line from the top connects the \( A_i \)-th (\( 1 \leq A_i \)) vertical line and the \( A_i + 1 \)-th vertical line.

An example of an Amida-kuji with \( N = 5 \), \( M = 7 \), and \( A = \{1, 4, 3, 4, 2, 3, 1\} \) is shown below. When drawing the lottery, choose one of the vertical lines and follow it from the top to the bottom. You must turn at every horizontal line encountered, and you cannot trace the vertical lines upwards. For example, starting from the 4th vertical line in this Amida-kuji, you will end up at the 3rd vertical line.

So far, this is a standard Amida-kuji. However, in recent times, the term "big data" is often mentioned. For Amida-kuji to survive, it must also become big to compete with big data.

Therefore, let's consider creating a giant Amida-kuji by connecting \( D \) Amida-kujis vertically. For example, connecting the previously mentioned Amida-kuji twice results in the following. In this case, starting from the 4th vertical line, you will end up at the 5th vertical line.

Although this giant Amida-kuji is created, it loses its meaning if it cannot fulfill its original purpose. That is, we need to efficiently calculate the result of drawing the lottery using this giant Amida-kuji.

Thus, for all integers \( k \) satisfying \( 1 \leq k \leq N \), write a program that calculates the final position at the bottom when starting from the \( k \)-th vertical line of the giant Amida-kuji.

Input Format

The input is given from the standard input in the following format:

\( N \) \( M \) \( D \) \( A_1 \) \( A_2 \) \( ... \) \( A_M \)

• The first line contains integers \( N \) (\( 2 \leq N \leq 10^5 \)), \( M \) (\( 0 \leq M \leq 2 \times 10^5 \)), and \( D \) (\( 1 \leq D \leq 10^9 \)), representing the number of vertical lines, the number of horizontal lines, and the number of times the original Amida-kuji is connected vertically, respectively.
• The second line contains \( M \) integers \( A_i \) (\( 1 \leq i \leq M \)), representing the information about the horizontal lines in the original Amida-kuji.

Output Format

Output \( N \) lines. The \( k \)-th line should contain an integer representing the final position at the bottom when starting from the \( k \)-th vertical line of the giant Amida-kuji.

Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

5 7 1
1 4 3 4 2 3 1

Sample Output #1

4
2
5
3
1

Sample Input #2

5 7 2
1 4 3 4 2 3 1

Sample Output #2

3
2
1
5
4

Sample Input #3

10 20 300
9 1 2 5 8 1 9 3 5 6 4 5 4 6 8 3 2 7 9 6

Sample Output #3

3
7
2
4
5
9
6
1
8
10

Notes/Hints

Partial Points

The test cases for this problem are divided into 4 groups, each with a specified score.

• In the first group, test cases satisfy \( D = 1 \). Correctly solving all test cases in this group awards 10 points.
• In the second group, test cases satisfy \( N \leq 1,000 \) and \( D \leq 1,000 \). Correctly solving all test cases in this group awards 20 points.
• In the third group, test cases satisfy \( N \leq 8 \). Correctly solving all test cases in this group awards 20 points.
• In the fourth group, there are no additional restrictions on the test cases. Correctly solving all test cases in this group awards 50 points.

Sample Explanation 1

This input/output example corresponds to the Amida-kuji shown in the first figure in the problem statement.

Sample Explanation 2

This input/output example corresponds to the Amida-kuji shown in the second figure in the problem statement. Note that this case does not satisfy the constraints of the first test group.

Sample Explanation 3

Note that this case does not satisfy the constraints of the first and third test groups.

见题面 Input 部分

见题面 Output 部分