Є парк із $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$.