Problem Description

Given a sequence of length $N$, divide it into subsequences such that each subsequence contains exactly $K$ numbers (guaranteed that $K$ is divisible by $N$). There are two types of operations:

• One: Shift each subsequence's numbers left/right by $X$ positions.
• Two: Shift the entire sequence left/right by $X$ positions.

Note that only operation two can change the numbers within the subsequences.

Given the final sequence after all operations and the operations themselves, you are asked to find the original sequence.

Input Format

The first line contains three positive integers $N, K, Q$, representing the length of the sequence after operations, the length of each subsequence, and the number of operations, respectively.

The next $Q$ lines each contain two positive integers $A_i$ and $X_i$, representing the type of operation and the number of positions to shift. $X > 0$ indicates a right shift, and $X < 0$ indicates a left shift.

The last line contains $N$ integers $Z_i$, representing the sequence after all operations.

Output Format

Output a single line containing $N$ integers, representing the original sequence.

Sample Input and Output

Sample Input #1

4 2 2
2 2
1 1
3 2 1 0

Sample Output #1

0 1 2 3

Sample Input #2

8 4 4
1 3
1 15
1 -5
2 -1
6 10 14 19 2 16 17 1

Sample Output #2

6 10 14 1 2 16 17 19

Sample Input #3

9 3 5
1 1
2 -8
2 9
1 1
2 -4
3 1 8 7 4 5 2 6 9

Sample Output #3

5 3 6 9 7 1 8 2 4

Notes

[Sample Explanation #1]

The starting sequence is $[0, 1, 2, 3]$. After the first operation, it becomes $[2, 3, 0, 1]$. After the second operation, it becomes $[3, 2, 1, 0]$.

[Data Range]

For $40\%$ of the data, $1 \le N \le 100$.

For $70\%$ of the data, $1 \le K \le 100$.

For $100\%$ of the data, $1 \le N \le 10^5$, $1 \le K \le 10^5$, $1 \le Q \le 10^5$, $1 \le A_i \le 2$, $-10^5 \le X_i \le 10^5$, $0 \le Z_i \le 10^5$.

[Explanation]

This problem's score is set according to the original COCI contest, with a maximum score of $140$.

The problem is translated from COCI2012_2013 CONTEST #5 T5 ROTIRAJ.

见题面 Input 部分

见题面 Output 部分