C'è un parco con $N$ piazze disposte in fila da sinistra a destra, numerate $0, 1, \dots, N - 1$ in quest'ordine.
All'interno del parco ci sono $N$ persone, anch'esse numerate $0, 1, \dots, N - 1$. Quando annunci una sequenza $X = (X_1, X_2, \dots, X_{|X|})$ di interi non negativi compresi tra $0$ e $N - 1$, le persone eseguono una marcia secondo le seguenti regole:
- Per ogni $i = 0, 1, \dots, N - 1$, la persona $i$ si sposta nella piazza $i$.
- Per ogni $j = 1, 2, \dots, |X|$, in quest'ordine, esegui quanto segue:
- Ogni persona che non si trova attualmente nella piazza $X_j$ si sposta di esattamente una piazza verso $X_j$.
Ti viene data una sequenza $A = (A_0, A_1, \dots, A_{M-1})$ di lunghezza $M$, composta da interi compresi tra $0$ e $N - 1$.
Devi rispondere a $Q$ query online. Per ogni $i = 1, 2, \dots, Q$, vengono dati gli interi $t'_i, L'_i, R'_i, P'_i$. Per prima cosa, ricostruisci $t_i, L_i, R_i, P_i$ utilizzando la seguente procedura:
Sia $\text{ans}_0 = 0$, e sia $\text{ans}_i$ la risposta alla $i$-esima query. Ricostruisci $t_i, L_i, R_i, P_i$ come segue:
- $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)$
Qui, per un intero non negativo $a$ e un intero positivo $b$, $(a \bmod b)$ indica il resto della divisione di $a$ per $b$, che è compreso nell'intervallo da $0$ a $b - 1$.
Per ciascuna quaterna ricostruita $(t_i, L_i, R_i, P_i)$, rispondi alla seguente query:
- Se $t_i = 0$: Sia $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simula la marcia e stampa la piazza finale in cui termina la persona $P_i$.
- Se $t_i = 1$: Sia $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simula la marcia e stampa quante persone terminano nella piazza $P_i$.
Input
L'input è fornito nel seguente 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- Tutti i valori di input sono interi.
- $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
Stampa $Q$ righe. Per ogni $i = 1, 2, \dots, Q$, stampa $\text{ans}_i$, la risposta alla $i$-esima query.
Esempi
Input di esempio 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Output di esempio 1
2 0 3
Input di esempio 2
7 4 1 3 3 3 3 1 3 0 3
Output di esempio 2
7
Note
Nella prima query dell'esempio 1, per $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ con $X = (2, 3, 2)$, la persona $2$ si muove come $2 \to 2 \to 3 \to 2$, quindi la risposta è $2$.
Nella seconda query dell'esempio 1, per $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ con $X = (3, 2, 1)$, il numero di persone nella piazza $3$ alla fine è $0$.
Nella terza query dell'esempio 1, per $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ con $X = (1)$, il numero di persone nella piazza $1$ alla fine è $3$.