توجد حديقة بها $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$.