ROTIRAJ

문제

Mislav and Marko have devised a new game, creatively named Rotate. First, Mirko imagines a number sequence of length N and divides it into sections, with each section containing K numbers (K evenly divides N). The first section contains numbers in the first K positions in the sequence, the second section the following K positions, and so on.

Then, Marko asks Mislav to apply a number of operations on the sequence, with each operation being one of the following two types:

1. Rotate the numbers in each section to the left/right by X positions
2. Rotate the whole sequence to the left/right by X positions

Notice that an operation of type 2 can change the numbers belonging to each section. After applying all the operations, Mislav reveals the final sequence to Marko. Marko's task is finding Mislav's starting sequence. He has asked you for help.

입력

The first line of input contains three positive integers: N (1 ≤ N ≤ 100 000), the length of the sequence, K (1 ≤ K ≤ 100 000), the size of each section, and Q (1 ≤ Q ≤ 100 000), the number of operations.

Each of the following Q lines contains two integers: A (1 ≤ A ≤ 2), the operation type, and X (-100 000 ≤ X ≤ 100 000), the number of positions to rotate by. A negative number represents rotation to the left, while a positive one represents rotation to the right.

The last line of input contains N space-separated integers Zi (0 ≤ Zi ≤ 100 000) representing the final sequence (after applying all operations).

출력

The first and only line of output must contain the required starting sequence.

 

힌트

Clarification of the first example: The starting sequence is 0 1 2 3. After the first operations, the sequence is 2 3 0 1, and after the second operation, it becomes 3 2 1 0. Ths corresponds to the final sequence.

4 2 2
2 2
1 1
3 2 1 0

0 1 2 3

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

6 10 14 1 2 16 17 19

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

5 3 6 9 7 1 8 2 4