Terdapat sebuah taman dengan $N$ alun-alun yang tersusun dalam satu baris dari kiri ke kanan, dinomori $0, 1, \dots, N - 1$ sesuai urutan tersebut.
Di dalam taman, terdapat $N$ orang, yang juga dinomori $0, 1, \dots, N - 1$. Ketika Anda mengumumkan sebuah barisan $X = (X_1, X_2, \dots, X_{|X|})$ yang terdiri dari bilangan-bilangan bulat tak negatif antara $0$ dan $N - 1$, orang-orang tersebut melakukan baris-berbaris sesuai aturan berikut:
- Untuk setiap $i = 0, 1, \dots, N - 1$, orang $i$ berpindah ke alun-alun $i$.
- Untuk setiap $j = 1, 2, \dots, |X|$, sesuai urutan ini, lakukan hal berikut:
- Setiap orang yang saat ini tidak berada di alun-alun $X_j$ bergerak tepat satu alun-alun mendekati $X_j$.
Anda diberikan sebuah barisan $A = (A_0, A_1, \dots, A_{M-1})$ sepanjang $M$, yang terdiri dari bilangan-bilangan bulat antara $0$ dan $N - 1$.
Anda harus menjawab $Q$ kueri daring (online). Untuk setiap $i = 1, 2, \dots, Q$, diberikan bilangan-bilangan bulat $t'_i, L'_i, R'_i, P'_i$. Pertama, rekonstruksi $t_i, L_i, R_i, P_i$ menggunakan prosedur berikut:
Misalkan $\text{ans}_0 = 0$, dan misalkan $\text{ans}_i$ menyatakan jawaban untuk kueri ke-$i$. Rekonstruksi $t_i, L_i, R_i, P_i$ sebagai berikut:
- $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)$
Di sini, untuk bilangan bulat tak negatif $a$ dan bilangan bulat positif $b$, $(a \bmod b)$ menyatakan sisa pembagian ketika $a$ dibagi dengan $b$, yang berada dalam rentang $0$ hingga $b - 1$.
Untuk setiap $(t_i, L_i, R_i, P_i)$ yang telah direkonstruksi, jawablah kueri berikut:
- Jika $t_i = 0$: Misalkan $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulasikan baris-berbaris tersebut dan keluarkan alun-alun akhir tempat orang $P_i$ berada.
- Jika $t_i = 1$: Misalkan $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulasikan baris-berbaris tersebut dan keluarkan berapa banyak orang yang berakhir di alun-alun $P_i$.
Masukan
Masukan diberikan dalam format berikut:
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- Semua nilai masukan adalah bilangan bulat.
- $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$)
Keluaran
Keluarkan $Q$ baris. Untuk setiap $i = 1, 2, \dots, Q$, keluarkan $\text{ans}_i$, yaitu jawaban untuk kueri ke-$i$.
Contoh
Contoh Masukan 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Contoh Keluaran 1
2 0 3
Contoh Masukan 2
7 4 1 3 3 3 3 1 3 0 3
Contoh Keluaran 2
7
Catatan
Pada kueri pertama Contoh 1, untuk $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ dengan $X = (2, 3, 2)$, orang $2$ bergerak sebagai $2 \to 2 \to 3 \to 2$, sehingga jawabannya adalah $2$.
Pada kueri kedua Contoh 1, untuk $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ dengan $X = (3, 2, 1)$, banyaknya orang di alun-alun $3$ pada akhirnya adalah $0$.
Pada kueri ketiga Contoh 1, untuk $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ dengan $X = (1)$, banyaknya orang di alun-alun $1$ pada akhirnya adalah $3$.