Það er garður með $N$ torgum sem raðað er í röð frá vinstri til hægri, númeruðum $0, 1, \dots, N - 1$ í þessari röð.
Inni í garðinum eru $N$ manneskjur, einnig númeraðar $0, 1, \dots, N - 1$. Þegar þú tilkynnir runu $X = (X_1, X_2, \dots, X_{|X|})$ af óneikvæðum heiltölum á milli $0$ og $N - 1$, framkvæmir fólkið göngu samkvæmt eftirfarandi reglum:
- Fyrir hvert $i = 0, 1, \dots, N - 1$ færir manneskja $i$ sig á torg $i$.
- Fyrir hvert $j = 1, 2, \dots, |X|$, í þessari röð, er eftirfarandi gert:
- Hver manneskja sem er ekki á torgi $X_j$ í augnablikinu færir sig um nákvæmlega eitt torg í átt að $X_j$.
Gefin er runa $A = (A_0, A_1, \dots, A_{M-1})$ af lengd $M$, sem samanstendur af heiltölum á milli $0$ og $N - 1$.
Þú verður að svara $Q$ beinlínufyrirspurnum (online queries). Fyrir hvert $i = 1, 2, \dots, Q$ eru gefnar heiltölurnar $t'_i, L'_i, R'_i, P'_i$. Fyrst skaltu endurgera $t_i, L_i, R_i, P_i$ með eftirfarandi aðferð:
Látum $\text{ans}_0 = 0$ og látum $\text{ans}_i$ tákna svarið við $i$-tu fyrirspurninni. Endurgerðu $t_i, L_i, R_i, P_i$ sem hér segir:
- $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)$
Hér, fyrir óneikvæða heiltölu $a$ og jákvæða heiltölu $b$, táknar $(a \bmod b)$ afganginn þegar $a$ er deilt með $b$, sem er á bilinu $0$ til $b - 1$.
Fyrir hvert endurgert $(t_i, L_i, R_i, P_i)$ skaltu svara eftirfarandi fyrirspurn:
- Ef $t_i = 0$: Látum $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Hermaðu eftir göngunni og prentaðu lokatorgið þar sem manneskja $P_i$ endar.
- Ef $t_i = 1$: Látum $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Hermaðu eftir göngunni og prentaðu hversu margar manneskjur enda á torgi $P_i$.
Inntak
Inntakið er gefið á eftirfarandi sniði:
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- Öll inntaksgildi eru heiltölur.
- $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$)
Úttak
Prentaðu $Q$ línur. Fyrir hvert $i = 1, 2, \dots, Q$, prentaðu $\text{ans}_i$, svarið við $i$-tu fyrirspurninni.
Dæmi
Dæmi um inntak 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Dæmi um úttak 1
2 0 3
Dæmi um inntak 2
7 4 1 3 3 3 3 1 3 0 3
Dæmi um úttak 2
7
Athugasemd
Í fyrstu fyrirspurninni í dæmi 1, fyrir $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ með $X = (2, 3, 2)$, færist manneskja $2$ sem $2 \to 2 \to 3 \to 2$, svo svarið er $2$.
Í annarri fyrirspurninni í dæmi 1, fyrir $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ með $X = (3, 2, 1)$, er fjöldi manneskja á torgi $3$ í lokin $0$.
Í þriðju fyrirspurninni í dæmi 1, fyrir $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ með $X = (1)$, er fjöldi manneskja á torgi $1$ í lokin $3$.