有一個公園,入面有 $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$ 嘅方向移動啱啱好一個廣場。
畀定一個長度為 $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- 所有輸入數值都係整數。
- $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$。