左から右へ一列に並んだ $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$ です。