AT_stpc2025_1_m Many Approaches

$ 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 $ にいる人数を答えてください。

入力は以下の形式で与えられる。 > $ N $ $ M $ $ Q $ $ A_0 $ $ A_1 $ $ \dots $ $ A_{M-1} $ $ t_1' $ $ L_1' $ $ R_1' $ $ P_1' $ $ t_2' $ $ L_2' $ $ R_2' $ $ P_2' $ $ \vdots $ $ t_Q' $ $ L_Q' $ $ R_Q' $ $ P_Q' $

$ Q $ 行出力せよ。 $ i=1,2,\dots, Q $ について $ i $ 行目には $ i $ 番目のクエリに対する答え $ \mathrm{ans}_i $ を出力せよ。

### Sample Explanation 1 $ 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 $ です。 ### Constraints - 入力はすべて整数 - $ 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) $