ישנו פארק עם $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$ שאילתות מקוונות (online). עבור כל $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$.