มีสวนสาธารณะแห่งหนึ่งที่มีจัตุรัส $N$ แห่งเรียงเป็นแถวจากซ้ายไปขวา โดยมีหมายเลขกำกับเป็น $0, 1, \dots, N - 1$ ตามลำดับนี้
ภายในสวนมีคน $N$ คน ซึ่งมีหมายเลขกำกับเป็น $0, 1, \dots, N - 1$ เช่นกัน เมื่อคุณประกาศลำดับ $X = (X_1, X_2, \dots, X_{|X|})$ ของจำนวนเต็มไม่ลบที่อยู่ระหว่าง $0$ ถึง $N - 1$ ผู้คนจะเดินขบวนตามกฎต่อไปนี้:
- สำหรับแต่ละ $i = 0, 1, \dots, N - 1$ คนที่ $i$ จะเคลื่อนที่ไปยังจัตุรัสที่ $i$
- สำหรับแต่ละ $j = 1, 2, \dots, |X|$ ตามลำดับนี้ ให้ทำสิ่งต่อไปนี้:
- ทุกคนที่ไม่ได้อยู่ที่จัตุรัส $X_j$ ในขณะนั้น จะเคลื่อนที่เข้าหา $X_j$ เป็นระยะทางหนึ่งจัตุรัสพอดี
คุณได้รับลำดับ $A = (A_0, A_1, \dots, A_{M-1})$ ที่มีความยาว $M$ ซึ่งประกอบด้วยจำนวนเต็มที่อยู่ระหว่าง $0$ ถึง $N - 1$
คุณต้องตอบคำถามแบบออนไลน์จำนวน $Q$ คำถาม สำหรับแต่ละ $i = 1, 2, \dots, Q$ จะกำหนดจำนวนเต็ม $t'_i, L'_i, R'_i, P'_i$ มาให้ ขั้นแรก ให้สร้างค่า $t_i, L_i, R_i, P_i$ ขึ้นใหม่โดยใช้ขั้นตอนต่อไปนี้:
ให้ $\text{ans}_0 = 0$ และให้ $\text{ans}_i$ แทนคำตอบของคำถามที่ $i$ สร้างค่า $t_i, L_i, R_i, P_i$ ขึ้นใหม่ดังนี้:
- $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)$
ในที่นี้ สำหรับจำนวนเต็มไม่ลบ $a$ และจำนวนเต็มบวก $b$ สัญลักษณ์ $(a \bmod b)$ แทนเศษเหลือเมื่อนำ $a$ มาหารด้วย $b$ ซึ่งอยู่ในช่วงตั้งแต่ $0$ ถึง $b - 1$
สำหรับแต่ละ $(t_i, L_i, R_i, P_i)$ ที่สร้างขึ้นใหม่ จงตอบคำถามต่อไปนี้:
- ถ้า $t_i = 0$: ให้ $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$ จำลองการเดินขบวนและแสดงผลหมายเลขจัตุรัสสุดท้ายที่คนที่ $P_i$ ไปหยุดอยู่
- ถ้า $t_i = 1$: ให้ $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$ จำลองการเดินขบวนและแสดงผลว่ามีกี่คนที่ไปหยุดอยู่ที่จัตุรัส $P_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- ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
- $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$)
ข้อมูลส่งออก
แสดงผล $Q$ บรรทัด สำหรับแต่ละ $i = 1, 2, \dots, Q$ ให้แสดงผลค่า $\text{ans}_i$ ซึ่งเป็นคำตอบของคำถามที่ $i$
ตัวอย่าง
ข้อมูลนำเข้าตัวอย่าง 1
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
ข้อมูลส่งออกตัวอย่าง 1
2 0 3
ข้อมูลนำเข้าตัวอย่าง 2
7 4 1 3 3 3 3 1 3 0 3
ข้อมูลส่งออกตัวอย่าง 2
7
หมายเหตุ
ในคำถามแรกของตัวอย่างที่ 1 สำหรับ $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ ที่มี $X = (2, 3, 2)$ คนที่ $2$ จะเคลื่อนที่เป็น $2 \to 2 \to 3 \to 2$ ดังนั้นคำตอบคือ $2$
ในคำถามที่สองของตัวอย่างที่ 1 สำหรับ $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ ที่มี $X = (3, 2, 1)$ จำนวนคนที่อยู่บนจัตุรัส $3$ ในตอนท้ายคือ $0$
ในคำถามที่สามของตัวอย่างที่ 1 สำหรับ $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ ที่มี $X = (1)$ จำนวนคนที่อยู่บนจัตุรัส $1$ ในตอนท้ายคือ $3$