問題文

N 個の広場が左右一列に並んだ公園があり、広場には左から順に 0,1,\dots, N-1 の番号が付けられています。

公園の中に、0, 1, \dots, N-1 の番号が付けられた N 人の人がいます。あなたが 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 に向けて広場 1 つ分だけ移動する。

0 以上 N-1 以下の非負整数からなる長さ M の列 A=(A_0,A_1,\dots, A_{M-1}) が与えられます。

Q 個のクエリにオンラインで答えてください。 i=1,2,\dots, Q について、 i 番目のクエリでは整数 t_i',L_i',R_i',P_i' が与えられます。まず、次の手順で t_i,L_i,R_i,P_i を復元してください。

• \mathrm{ans}_0=0 、\mathrm{ans}_i= ( i 番目のクエリの答え) とする。
• このとき、次のように t_i,L_i,R_i,P_i を復元する。
  • t_i=((t_i' + \mathrm{ans}_{i-1})\bmod 2)
  • a=((L_i' + \mathrm{ans}_{i-1})\bmod M)
  • b=((R_i' + \mathrm{ans}_{i-1})\bmod M)
  • L_i=\min(a,b)
  • R_i=\max(a,b)
  • P_i=((P_i' + \mathrm{ans}_{i-1})\bmod N)

ここで非負整数 a と正整数 b に対して (a\bmod b) は a を b で割ったあまりを表します。この値は 0 以上 b 未満です。

このようにして得られた 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 にいる人数を答えてください。

制約

• 入力はすべて整数
• 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

1 番目のクエリでは (t_i,L_i,R_i,P_i)=(0,1,3,2) です。 X = (A_1,A_2,A_3)=(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 = (A_2,A_3,A_4)=(3,2,1) を宣言して行進を行ったとき、最終的に各広場にいる人の人数は広場 0 から順に 0,4,0,0 です。よって答えは 0 です。

3 番目のクエリでは (t_i,L_i,R_i,P_i)=(1,4,4,1) です。 X = (A_4)=(1) を宣言して行進を行ったとき、最終的に各広場にいる人の人数は広場 0 から順に 0,3,1,0 です。よって答えは 3 です。

入力例 2

7 4 1
3 3 3 3
1 3 0 3

出力例 2

7