왼쪽에서 오른쪽으로 일렬로 배열된 $N$개의 광장이 있는 공원이 있으며, 순서대로 $0, 1, \dots, N - 1$의 번호가 매겨져 있습니다.
공원 안에는 $N$명의 사람이 있으며, 마찬가지로 $0, 1, \dots, N - 1$의 번호가 매겨져 있습니다. $0$ 이상 $N - 1$ 이하의 음이 아닌 정수들로 이루어진 수열 $X = (X_1, X_2, \dots, X_{|X|})$를 발표하면, 사람들은 다음 규칙에 따라 행진을 수행합니다:
- 각 $i = 0, 1, \dots, N - 1$에 대해, 사람 $i$는 광장 $i$로 이동합니다.
- 각 $j = 1, 2, \dots, |X|$에 대해, 이 순서대로 다음을 수행합니다:
- 현재 광장 $X_j$에 있지 않은 모든 사람은 광장 $X_j$ 방향으로 정확히 한 칸 이동합니다.
$0$ 이상 $N - 1$ 이하의 정수로 이루어진 길이 $M$인 수열 $A = (A_0, A_1, \dots, A_{M-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$에 대해 $i$번째 질의의 답인 $\text{ans}_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$입니다.