There is a park with $N$ squares arranged in a row from left to right, numbered $0, 1, \dots, N - 1$ in this order.
Inside the park, there are $N$ people, also numbered $0, 1, \dots, N - 1$. When you announce a sequence $X = (X_1, X_2, \dots, X_{|X|})$ of non-negative integers between $0$ and $N - 1$, the people perform a march according to the following rules:
- For each $i = 0, 1, \dots, N - 1$, person $i$ moves to square $i$.
- For each $j = 1, 2, \dots, |X|$, in this order, do the following:
- Every person not currently on square $X_j$ moves exactly one square toward $X_j$.
You are given a sequence $A = (A_0, A_1, \dots, A_{M-1})$ of length $M$, consisting of integers between $0$ and $N - 1$.
You must answer $Q$ online queries. For each $i = 1, 2, \dots, Q$, integers $t'_i, L'_i, R'_i, P'_i$ are given. First, reconstruct $t_i, L_i, R_i, P_i$ using the following procedure:
Let $\text{ans}_0 = 0$, and let $\text{ans}_i$ denote the answer to the $i$-th query. Reconstruct $t_i, L_i, R_i, P_i$ as follows:
- $t_i = ((t'_i + \text{ans}_{i-1}) \bmod 2)$
- $a = ((L'_i + \text{ans}_{i-1}) \bmod M)$
- $b = ((R'_i + \text{ans}_{i-1}) \bmod M)$
- $L_i = \min(a, b)$
- $R_i = \max(a, b)$
- $P_i = ((P'_i + \text{ans}_{i-1}) \bmod N)$
Here, for a non-negative integer $a$ and a positive integer $b$, $(a \bmod b)$ denotes the remainder when $a$ is divided by $b$, which is in the range $0$ through $b - 1$.
For each reconstructed $(t_i, L_i, R_i, P_i)$, answer the following query:
- If $t_i = 0$: Let $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulate the march and output the final square where person $P_i$ ends up.
- If $t_i = 1$: Let $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulate the march and output how many people end up on square $P_i$.
Input
The input is given in the following format:
N M Q
A_0 A_1 ... A_{M-1}
t'_1 L'_1 R'_1 P'_1
t'_2 L'_2 R'_2 P'_2
:
t'_Q L'_Q R'_Q P'_Q- All input values are integers.
- $1 \le N, M, Q \le 2 \times 10^5$
- $0 \le A_i \le N - 1$ ($0 \le i \le M - 1$)
- $0 \le t'_i, t_i \le 1$ ($1 \le i \le Q$)
- $0 \le L'_i, R'_i \le M - 1$ ($1 \le i \le Q$)
- $0 \le L_i \le R_i \le M - 1$ ($1 \le i \le Q$)
- $0 \le P'_i, P_i \le N - 1$ ($1 \le i \le Q$)
Output
Output $Q$ lines. For each $i = 1, 2, \dots, Q$, output $\text{ans}_i$, the answer to the $i$-th query.
Examples
Sample Input 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Sample Output 1
2 0 3
Sample Input 2
7 4 1 3 3 3 3 1 3 0 3
Sample Output 2
7
Note
In the first query of Sample 1, for $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ with $X = (2, 3, 2)$, person $2$ moves as $2 \to 2 \to 3 \to 2$, so the answer is $2$.
In the second query of Sample 1, for $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ with $X = (3, 2, 1)$, the number of people on square $3$ at the end is $0$.
In the third query of Sample 1, for $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ with $X = (1)$, the number of people on square $1$ at the end is $3$.