400547: GYM100203 F Find the sequence

Mislav and Marko have devised a new game, creatively named Rotate. First, Marko 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 ≤ 10⁵), the length of the sequence, K (1 ≤ K ≤ 10⁵), the size of each section, and Q (1 ≤ Q ≤ 10⁵), the number of operations.

Each of the following Q lines contains two integers: A (1 ≤ A ≤ 2), the operation type, and X ( - 10⁵ ≤ X ≤ 10⁵), 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 Z_i (0 ≤ Z_i ≤ 10⁵) representing the final sequence (after applying all operations).

The first and only line of output must contain the required starting 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 

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