有一个公园，里面有 $N$ 个广场，从左到右排成一排，依次编号为 $0, 1, \dots, N - 1$。

公园里有 $N$ 个人，也依次编号为 $0, 1, \dots, N - 1$。当你宣布一个由介于 $0$ 到 $N - 1$ 之间的非负整数组成的序列 $X = (X_1, X_2, \dots, X_{|X|})$ 时，所有人将按照以下规则进行行进：

1. 对于每个 $i = 0, 1, \dots, N - 1$，第 $i$ 个人移动到广场 $i$。

2. 对于每个 $j = 1, 2, \dots, |X|$，按此顺序执行以下操作：

   • 所有当前不在广场 $X_j$ 上的每个人，都向 $X_j$ 的方向移动恰好一个广场。

给你一个长度为 $M$ 的序列 $A = (A_0, A_1, \dots, A_{M-1})$，由介于 $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

输出格式

输出 $Q$ 行。对于每个 $i = 1, 2, \dots, Q$，输出 $\text{ans}_i$，即第 $i$ 个查询的答案。

数据范围

• 所有输入值均为整数。
• $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$)

样例

输入样例 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$。
• 对于第 2 个查询，$(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$，对应的 $X = (3, 2, 1)$。最终停留在广场 $3$ 上的总人数为 $0$。
• 对于第 3 个查询，$(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$，对应的 $X = (1)$。最终停留在广场 $1$ 上的总人数为 $3$。