Puistossa on $N$ aukiota, jotka on järjestetty riviin vasemmalta oikealle ja numeroitu tässä järjestyksessä $0, 1, \dots, N - 1$.
Puistossa on $N$ henkilöä, jotka on myös numeroitu $0, 1, \dots, N - 1$. Kun ilmoitat epänegatiivisista kokonaisluvuista väliltä $0$ – $N - 1$ koostuvan jonon $X = (X_1, X_2, \dots, X_{|X|})$, henkilöt suorittavat marssin seuraavien sääntöjen mukaisesti:
- Jokaiselle $i = 0, 1, \dots, N - 1$, henkilö $i$ siirtyy aukiolle $i$.
- Jokaiselle $j = 1, 2, \dots, |X|$, tässä järjestyksessä, tehdään seuraavaa:
- Jokainen henkilö, joka ei tällä hetkellä ole aukiolla $X_j$, siirtyy täsmälleen yhden aukion verran kohti aukiota $X_j$.
Annettuna on pituutta $M$ oleva jono $A = (A_0, A_1, \dots, A_{M-1})$, joka koostuu kokonaisluvuista väliltä $0$ – $N - 1$.
Sinun on vastattava $Q$ online-kyselyyn. Jokaiselle $i = 1, 2, \dots, Q$ annetaan kokonaisluvut $t'_i, L'_i, R'_i, P'_i$. Muodosta ensin luvut $t_i, L_i, R_i, P_i$ seuraavalla menettelyllä:
Olkoon $\text{ans}_0 = 0$, ja tarkoittakoon $\text{ans}_i$ vastausta $i$:nteen kyselyyn. Muodosta $t_i, L_i, R_i, P_i$ seuraavasti:
- $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)$
Tässä epänegatiiviselle kokonaisluvulle $a$ ja positiiviselle kokonaisluvulle $b$ merkintä $(a \bmod b)$ tarkoittaa jakojäännöstä, kun $a$ jaetaan $b$:llä, mikä on välillä $0$ – $b - 1$.
Vastaa jokaiselle muodostetulle nelikolle $(t_i, L_i, R_i, P_i)$ seuraavaan kyselyyn:
- Jos $t_i = 0$: Olkoon $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuloi marssi ja tulosta aukio, jolle henkilö $P_i$ lopulta päätyy.
- Jos $t_i = 1$: Olkoon $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simuloi marssi ja tulosta, kuinka monta henkilöä päätyy lopulta aukiolle $P_i$.
Syöte
Syöte annetaan seuraavassa muodossa:
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- Kaikki syötteen arvot ovat kokonaislukuja.
- $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$)
Tuloste
Tulosta $Q$ riviä. Jokaiselle $i = 1, 2, \dots, Q$, tulosta $\text{ans}_i$, vastaus $i$:nteen kyselyyn.
Esimerkit
Esimerkkisyöte 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Esimerkkituloste 1
2 0 3
Esimerkkisyöte 2
7 4 1 3 3 3 3 1 3 0 3
Esimerkkituloste 2
7
Huomautus
Esimerkin 1 ensimmäisessä kyselyssä nelikolla $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ ja jonolla $X = (2, 3, 2)$ henkilö $2$ liikkuu $2 \to 2 \to 3 \to 2$, joten vastaus on $2$.
Esimerkin 1 toisessa kyselyssä nelikolla $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ ja jonolla $X = (3, 2, 1)$ aukiolla $3$ olevien henkilöiden määrä lopussa on $0$.
Esimerkin 1 kolmannessa kyselyssä nelikolla $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ ja jonolla $X = (1)$ aukiolla $1$ olevien henkilöiden määrä lopussa on $3$.