Es gibt einen Park mit $N$ Plätzen, die in einer Reihe von links nach rechts angeordnet und in dieser Reihenfolge mit $0, 1, \dots, N - 1$ nummeriert sind.
Im Park befinden sich $N$ Personen, die ebenfalls mit $0, 1, \dots, N - 1$ nummeriert sind. Wenn du eine Folge $X = (X_1, X_2, \dots, X_{|X|})$ aus nichtnegativen ganzen Zahlen zwischen $0$ und $N - 1$ bekanntgibst, führen die Personen einen Marsch nach den folgenden Regeln durch:
- Für jedes $i = 0, 1, \dots, N - 1$ begibt sich Person $i$ auf Platz $i$.
- Für jedes $j = 1, 2, \dots, |X|$ wird in dieser Reihenfolge Folgendes ausgeführt:
- Jede Person, die sich derzeit nicht auf Platz $X_j$ befindet, bewegt sich genau einen Platz in Richtung $X_j$.
Gegeben ist eine Folge $A = (A_0, A_1, \dots, A_{M-1})$ der Länge $M$, die aus ganzen Zahlen zwischen $0$ und $N - 1$ besteht.
Du musst $Q$ Online-Anfragen beantworten. Für jedes $i = 1, 2, \dots, Q$ sind ganze Zahlen $t'_i, L'_i, R'_i, P'_i$ gegeben. Rekonstruiere zunächst $t_i, L_i, R_i, P_i$ mit dem folgenden Verfahren:
Sei $\text{ans}_0 = 0$, und sei $\text{ans}_i$ die Antwort auf die $i$-te Anfrage. Rekonstruiere $t_i, L_i, R_i, P_i$ wie folgt:
- $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)$
Hierbei bezeichnet $(a \bmod b)$ für eine nichtnegative ganze Zahl $a$ und eine positive ganze Zahl $b$ den Rest bei der Division von $a$ durch $b$, der im Bereich von $0$ bis $b - 1$ liegt.
Beantworte für jedes rekonstruierte Tupel $(t_i, L_i, R_i, P_i)$ die folgende Anfrage:
- Wenn $t_i = 0$: Sei $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuliere den Marsch und gib den Platz aus, auf dem Person $P_i$ am Ende landet.
- Wenn $t_i = 1$: Sei $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuliere den Marsch und gib aus, wie viele Personen am Ende auf Platz $P_i$ landen.
Eingabe
Die Eingabe erfolgt im folgenden 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- Alle Eingabewerte sind ganze Zahlen.
- $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$)
Ausgabe
Gib $Q$ Zeilen aus. Gib für jedes $i = 1, 2, \dots, Q$ den Wert $\text{ans}_i$ aus, die Antwort auf die $i$-te Anfrage.
Beispiele
Beispieleingabe 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Beispielausgabe 1
2 0 3
Beispieleingabe 2
7 4 1 3 3 3 3 1 3 0 3
Beispielausgabe 2
7
Hinweis
In der ersten Anfrage von Beispiel 1 bewegt sich für $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ mit $X = (2, 3, 2)$ die Person $2$ gemäß $2 \to 2 \to 3 \to 2$, also lautet die Antwort $2$.
In der zweiten Anfrage von Beispiel 1 beträgt für $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ mit $X = (3, 2, 1)$ die Anzahl der Personen auf Platz $3$ am Ende $0$.
In der dritten Anfrage von Beispiel 1 beträgt für $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ mit $X = (1)$ die Anzahl der Personen auf Platz $1$ am Ende $3$.