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:
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 ≤ 105), the length of the sequence, K (1 ≤ K ≤ 105), the size of each section, and Q (1 ≤ Q ≤ 105), the number of operations.
Each of the following Q lines contains two integers: A (1 ≤ A ≤ 2), the operation type, and X ( - 105 ≤ X ≤ 105), 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 ≤ 105) 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 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.
## Input
The first line of input contains three positive integers: N (1 ≤ N ≤ 105), the length of the sequence, K (1 ≤ K ≤ 105), the size of each section, and Q (1 ≤ Q ≤ 105), the number of operations.Each of the following Q lines contains two integers: A (1 ≤ A ≤ 2), the operation type, and X ( - 105 ≤ X ≤ 105), 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 ≤ 105) representing the final sequence (after applying all operations).
## Output
The first and only line of output must contain the required starting sequence.
[samples]
## Note
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.
**Definitions**
Let $ N, K, Q \in \mathbb{Z}^+ $ with $ K \mid N $.
Let $ Z = (z_1, z_2, \dots, z_N) \in \mathbb{Z}^N $ be the final sequence.
Let the sequence be partitioned into $ m = \frac{N}{K} $ contiguous sections $ S_1, S_2, \dots, S_m $, where $ S_j = (a_{(j-1)K+1}, \dots, a_{jK}) $.
Each operation is a **section-wise rotation**:
- Type 1: Rotate section $ \left\lceil \frac{X}{K} \right\rceil $ by $ X \mod K $ positions (right if positive, left if negative).
- Type 2: Rotate **all** sections **simultaneously** by $ X $ positions **cyclically** (i.e., shift section indices: section $ i $ moves to position $ i + X \mod m $).
Let $ O = (o_1, \dots, o_Q) $ be the sequence of operations, where each $ o_i = (A_i, X_i) $.
**Constraints**
1. $ 1 \leq N \leq 10^5 $, $ 1 \leq K \leq 10^5 $, $ K \mid N $, $ 1 \leq Q \leq 10^5 $
2. $ -10^5 \leq X_i \leq 10^5 $ for all $ i $
3. $ 0 \leq z_i \leq 10^5 $ for all $ i \in \{1, \dots, N\} $
**Objective**
Recover the initial sequence $ A = (a_1, \dots, a_N) $ such that applying operations $ o_1, \dots, o_Q $ in order yields $ Z $.
Equivalently, **invert** the composition of operations:
Let $ T = o_Q \circ \cdots \circ o_1 $ be the total transformation.
Then $ A = T^{-1}(Z) $.
Compute $ A $ by applying the **inverse** of each operation in **reverse order**.