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.

Input Specification

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

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

Output Specification

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

Scoring

In test data worth at least ~40\%~ of total points, ~N~ will be at most ~100~.

In test data worth at least ~70\%~ of total points, ~K~ will be at most ~100~.

Sample Input 1

4 2 2
2 2
1 1
3 2 1 0

Sample Output 1

0 1 2 3

Explanation for Sample Output 1

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~. This corresponds to the final sequence.

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