Il y a un parc comportant $N$ places disposées en ligne de gauche à droite, numérotées $0, 1, \dots, N - 1$ dans cet ordre.
À l'intérieur du parc, il y a $N$ personnes, également numérotées $0, 1, \dots, N - 1$. Lorsque vous annoncez une séquence $X = (X_1, X_2, \dots, X_{|X|})$ d'entiers naturels compris entre $0$ et $N - 1$, les personnes effectuent une marche selon les règles suivantes :
- Pour chaque $i = 0, 1, \dots, N - 1$, la personne $i$ se déplace sur la place $i$.
- Pour chaque $j = 1, 2, \dots, |X|$, dans cet ordre, effectuez l'opération suivante :
- Chaque personne qui ne se trouve pas actuellement sur la place $X_j$ se déplace d'exactement une place en direction de $X_j$.
On vous donne une séquence $A = (A_0, A_1, \dots, A_{M-1})$ de longueur $M$, constituée d'entiers compris entre $0$ et $N - 1$.
Vous devez répondre à $Q$ requêtes en ligne (online). Pour chaque $i = 1, 2, \dots, Q$, des entiers $t'_i, L'_i, R'_i, P'_i$ sont donnés. Tout d'abord, reconstruisez $t_i, L_i, R_i, P_i$ à l'aide de la procédure suivante :
Soit $\text{ans}_0 = 0$, et soit $\text{ans}_i$ la réponse à la $i$-ième requête. Reconstruisez $t_i, L_i, R_i, P_i$ comme suit :
- $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)$
Ici, pour un entier naturel $a$ et un entier strictement positif $b$, $(a \bmod b)$ désigne le reste de la division euclidienne de $a$ par $b$, compris entre $0$ et $b - 1$.
Pour chaque quadruplet reconstruit $(t_i, L_i, R_i, P_i)$, répondez à la requête suivante :
- Si $t_i = 0$ : Soit $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulez la marche et affichez la place finale sur laquelle termine la personne $P_i$.
- Si $t_i = 1$ : Soit $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulez la marche et affichez combien de personnes terminent sur la place $P_i$.
Entrée
L'entrée est donnée dans le format suivant :
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- Toutes les valeurs d'entrée sont des entiers.
- $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$)
Sortie
Affichez $Q$ lignes. Pour chaque $i = 1, 2, \dots, Q$, affichez $\text{ans}_i$, la réponse à la $i$-ième requête.
Exemples
Exemple d'entrée 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Exemple de sortie 1
2 0 3
Exemple d'entrée 2
7 4 1 3 3 3 3 1 3 0 3
Exemple de sortie 2
7
Note
Dans la première requête de l'exemple 1, pour $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ avec $X = (2, 3, 2)$, la personne $2$ se déplace selon $2 \to 2 \to 3 \to 2$, donc la réponse est $2$.
Dans la deuxième requête de l'exemple 1, pour $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ avec $X = (3, 2, 1)$, le nombre de personnes sur la place $3$ à la fin est $0$.
Dans la troisième requête de l'exemple 1, pour $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ avec $X = (1)$, le nombre de personnes sur la place $1$ à la fin est $3$.