Есть парк с $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
Примечание
В первом запросе первого примера для $(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$.
Во втором запросе первого примера для $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ и $X = (3, 2, 1)$ количество людей на площади $3$ в конце равно $0$.
В третьем запросе первого примера для $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ и $X = (1)$ количество людей на площади $1$ в конце равно $3$.