Hay un parque con $N$ plazas dispuestas en fila de izquierda a derecha, numeradas $0, 1, \dots, N - 1$ en este orden.
Dentro del parque hay $N$ personas, también numeradas $0, 1, \dots, N - 1$. Cuando anuncias una secuencia $X = (X_1, X_2, \dots, X_{|X|})$ de enteros no negativos entre $0$ y $N - 1$, las personas realizan una marcha siguiendo estas reglas:
- Para cada $i = 0, 1, \dots, N - 1$, la persona $i$ se mueve a la plaza $i$.
- Para cada $j = 1, 2, \dots, |X|$, en este orden, se hace lo siguiente:
- Cada persona que no se encuentre actualmente en la plaza $X_j$ se mueve exactamente una plaza hacia $X_j$.
Se te da una secuencia $A = (A_0, A_1, \dots, A_{M-1})$ de longitud $M$, formada por enteros entre $0$ y $N - 1$.
Debes responder a $Q$ consultas en línea (online). Para cada $i = 1, 2, \dots, Q$, se dan los enteros $t'_i, L'_i, R'_i, P'_i$. Primero, reconstruye $t_i, L_i, R_i, P_i$ mediante el siguiente procedimiento:
Sea $\text{ans}_0 = 0$, y sea $\text{ans}_i$ la respuesta a la $i$-ésima consulta. Reconstruye $t_i, L_i, R_i, P_i$ como sigue:
- $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)$
Aquí, para un entero no negativo $a$ y un entero positivo $b$, $(a \bmod b)$ denota el resto de dividir $a$ entre $b$, que está en el rango de $0$ a $b - 1$.
Para cada $(t_i, L_i, R_i, P_i)$ reconstruido, responde a la siguiente consulta:
- Si $t_i = 0$: Sea $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simula la marcha e imprime la plaza final en la que termina la persona $P_i$.
- Si $t_i = 1$: Sea $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simula la marcha e imprime cuántas personas terminan en la plaza $P_i$.
Entrada
La entrada se proporciona en el siguiente formato:
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- Todos los valores de entrada son enteros.
- $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$)
Salida
Imprime $Q$ líneas. Para cada $i = 1, 2, \dots, Q$, imprime $\text{ans}_i$, la respuesta a la $i$-ésima consulta.
Ejemplos
Entrada de ejemplo 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Salida de ejemplo 1
2 0 3
Entrada de ejemplo 2
7 4 1 3 3 3 3 1 3 0 3
Salida de ejemplo 2
7
Nota
En la primera consulta del ejemplo 1, para $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ con $X = (2, 3, 2)$, la persona $2$ se mueve como $2 \to 2 \to 3 \to 2$, por lo que la respuesta es $2$.
En la segunda consulta del ejemplo 1, para $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ con $X = (3, 2, 1)$, el número de personas en la plaza $3$ al final es $0$.
En la tercera consulta del ejemplo 1, para $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ con $X = (1)$, el número de personas en la plaza $1$ al final es $3$.