W parku znajduje się $N$ placów ustawionych w rzędzie od lewej do prawej, ponumerowanych kolejno $0, 1, \dots, N - 1$.
W parku znajduje się $N$ osób, również ponumerowanych $0, 1, \dots, N - 1$. Gdy ogłaszasz ciąg $X = (X_1, X_2, \dots, X_{|X|})$ nieujemnych liczb całkowitych z przedziału od $0$ do $N - 1$, osoby wykonują marsz zgodnie z następującymi zasadami:
- Dla każdego $i = 0, 1, \dots, N - 1$, osoba $i$ przechodzi na plac $i$.
- Dla każdego $j = 1, 2, \dots, |X|$, w tej kolejności, wykonaj co następuje:
- Każda osoba, która nie znajduje się obecnie na placu $X_j$, przesuwa się dokładnie o jeden plac w kierunku $X_j$.
Dany jest ciąg $A = (A_0, A_1, \dots, A_{M-1})$ długości $M$, składający się z liczb całkowitych z przedziału od $0$ do $N - 1$.
Musisz odpowiedzieć na $Q$ zapytań online. Dla każdego $i = 1, 2, \dots, Q$ podane są liczby całkowite $t'_i, L'_i, R'_i, P'_i$. Najpierw odtwórz $t_i, L_i, R_i, P_i$ za pomocą następującej procedury:
Niech $\text{ans}_0 = 0$ oraz niech $\text{ans}_i$ oznacza odpowiedź na $i$-te zapytanie. Odtwórz $t_i, L_i, R_i, P_i$ w następujący sposób:
- $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)$
Tutaj, dla nieujemnej liczby całkowitej $a$ oraz dodatniej liczby całkowitej $b$, $(a \bmod b)$ oznacza resztę z dzielenia $a$ przez $b$, należącą do przedziału od $0$ do $b - 1$.
Dla każdej odtworzonej czwórki $(t_i, L_i, R_i, P_i)$ odpowiedz na następujące zapytanie:
- Jeśli $t_i = 0$: Niech $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Zasymuluj marsz i wypisz numer placu, na którym ostatecznie znajdzie się osoba $P_i$.
- Jeśli $t_i = 1$: Niech $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Zasymuluj marsz i wypisz, ile osób ostatecznie znajdzie się na placu $P_i$.
Wejście
Wejście jest podane w następującym formacie:
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- Wszystkie wartości wejściowe są liczbami całkowitymi.
- $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$)
Wyjście
Wypisz $Q$ wierszy. Dla każdego $i = 1, 2, \dots, Q$ wypisz $\text{ans}_i$, czyli odpowiedź na $i$-te zapytanie.
Przykłady
Przykładowe wejście 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Przykładowe wyjście 1
2 0 3
Przykładowe wejście 2
7 4 1 3 3 3 3 1 3 0 3
Przykładowe wyjście 2
7
Uwaga
W pierwszym zapytaniu z przykładu 1, dla $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ oraz $X = (2, 3, 2)$, osoba $2$ porusza się następująco: $2 \to 2 \to 3 \to 2$, więc odpowiedź wynosi $2$.
W drugim zapytaniu z przykładu 1, dla $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ oraz $X = (3, 2, 1)$, liczba osób na placu $3$ na końcu wynosi $0$.
W trzecim zapytaniu z przykładu 1, dla $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ oraz $X = (1)$, liczba osób na placu $1$ na końcu wynosi $3$.