Có một công viên gồm $N$ quảng trường được xếp thành một hàng từ trái sang phải, được đánh số $0, 1, \dots, N - 1$ theo thứ tự đó.
Bên trong công viên có $N$ người, cũng được đánh số $0, 1, \dots, N - 1$. Khi bạn công bố một dãy $X = (X_1, X_2, \dots, X_{|X|})$ gồm các số nguyên không âm nằm giữa $0$ và $N - 1$, mọi người sẽ thực hiện một cuộc diễu hành theo các quy tắc sau:
- Với mỗi $i = 0, 1, \dots, N - 1$, người thứ $i$ di chuyển đến quảng trường $i$.
- Với mỗi $j = 1, 2, \dots, |X|$, theo thứ tự này, thực hiện điều sau:
- Mỗi người hiện không ở tại quảng trường $X_j$ sẽ di chuyển đúng một quảng trường về phía $X_j$.
Bạn được cho một dãy $A = (A_0, A_1, \dots, A_{M-1})$ có độ dài $M$, gồm các số nguyên nằm giữa $0$ và $N - 1$.
Bạn phải trả lời $Q$ truy vấn trực tuyến (online). Với mỗi $i = 1, 2, \dots, Q$, các số nguyên $t'_i, L'_i, R'_i, P'_i$ được cho trước. Trước tiên, hãy khôi phục $t_i, L_i, R_i, P_i$ bằng quy trình sau:
Đặt $\text{ans}_0 = 0$, và gọi $\text{ans}_i$ là câu trả lời cho truy vấn thứ $i$. Khôi phục $t_i, L_i, R_i, P_i$ như sau:
- $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)$
Ở đây, với số nguyên không âm $a$ và số nguyên dương $b$, $(a \bmod b)$ biểu thị số dư khi chia $a$ cho $b$, nằm trong đoạn từ $0$ đến $b - 1$.
Với mỗi bộ $(t_i, L_i, R_i, P_i)$ đã khôi phục, hãy trả lời truy vấn sau:
- Nếu $t_i = 0$: Đặt $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Hãy mô phỏng cuộc diễu hành và in ra quảng trường cuối cùng mà người $P_i$ dừng lại.
- Nếu $t_i = 1$: Đặt $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Hãy mô phỏng cuộc diễu hành và in ra số lượng người kết thúc tại quảng trường $P_i$.
Dữ liệu vào
Dữ liệu vào được cho dưới định dạng sau:
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- Tất cả các giá trị đầu vào đều là số nguyên.
- $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$)
Kết quả
In ra $Q$ dòng. Với mỗi $i = 1, 2, \dots, Q$, in ra $\text{ans}_i$, là câu trả lời cho truy vấn thứ $i$.
Ví dụ
Dữ liệu vào mẫu 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
Kết quả mẫu 1
2 0 3
Dữ liệu vào mẫu 2
7 4 1 3 3 3 3 1 3 0 3
Kết quả mẫu 2
7
Ghi chú
Ở truy vấn thứ nhất của Ví dụ 1, với $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ và $X = (2, 3, 2)$, người $2$ di chuyển theo lộ trình $2 \to 2 \to 3 \to 2$, nên câu trả lời là $2$.
Ở truy vấn thứ hai của Ví dụ 1, với $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ và $X = (3, 2, 1)$, số người ở quảng trường $3$ vào cuối cuộc diễu hành là $0$.
Ở truy vấn thứ ba của Ví dụ 1, với $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ và $X = (1)$, số người ở quảng trường $1$ vào cuối cuộc diễu hành là $3$.