Det er en park med $N$ torg plassert på rekke fra venstre til høyre, nummerert $0, 1, \dots, N - 1$ i denne rekkefølgen.
Inne i parken er det $N$ personer, også nummerert $0, 1, \dots, N - 1$. Når du kunngjør en sekvens $X = (X_1, X_2, \dots, X_{|X|})$ av ikke-negative heltall mellom $0$ og $N - 1$, utfører personene en marsj etter følgende regler:
- For hver $i = 0, 1, \dots, N - 1$ flytter person $i$ seg til torg $i$.
- For hver $j = 1, 2, \dots, |X|$, i denne rekkefølgen, gjør følgende:
- Hver person som ikke befinner seg på torg $X_j$ for øyeblikket, flytter seg nøyaktig ett torg i retning mot $X_j$.
Du får gitt en sekvens $A = (A_0, A_1, \dots, A_{M-1})$ med lengde $M$, bestående av heltall mellom $0$ og $N - 1$.
Du må svare på $Q$ online-spørringer. For hver $i = 1, 2, \dots, Q$ er heltallene $t'_i, L'_i, R'_i, P'_i$ gitt. Rekonstruer først $t_i, L_i, R_i, P_i$ ved hjelp av følgende prosedyre:
La $\text{ans}_0 = 0$, og la $\text{ans}_i$ betegne svaret på den $i$-te spørringen. Rekonstruer $t_i, L_i, R_i, P_i$ slik:
- $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)$
Her, for et ikke-negativt heltall $a$ og et positivt heltall $b$, betegner $(a \bmod b)$ resten når $a$ deles på $b$, som ligger i området $0$ til $b - 1$.
For hver rekonstruerte $(t_i, L_i, R_i, P_i)$, svar på følgende spørring:
- Hvis $t_i = 0$: La $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuler marsjen og skriv ut det endelige torget der person $P_i$ ender opp.
- Hvis $t_i = 1$: La $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuler marsjen og skriv ut hvor mange personer som ender opp på torg $P_i$.
Inndata
Inndataene er gitt på følgende 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 inndataverdier er heltall.
- $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$)
Utdata
Skriv ut $Q$ linjer. For hver $i = 1, 2, \dots, Q$, skriv ut $\text{ans}_i$, svaret på den $i$-te spørringen.
Eksempler
Eksempelinndata 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Eksempelutdata 1
2 0 3
Eksempelinndata 2
7 4 1 3 3 3 3 1 3 0 3
Eksempelutdata 2
7
Merk
I den første spørringen i eksempel 1, for $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ med $X = (2, 3, 2)$, flytter person $2$ seg som $2 \to 2 \to 3 \to 2$, så svaret er $2$.
I den andre spørringen i eksempel 1, for $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ med $X = (3, 2, 1)$, er antallet personer på torg $3$ til slutt $0$.
I den tredje spørringen i eksempel 1, for $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ med $X = (1)$, er antallet personer på torg $1$ til slutt $3$.