問題文

これから、馬 $1,2,\dots ,N$ からなる $N$ 頭の馬によるレースが行われます。

レースは以下の形式に則ったものです。

• $N$ 頭の馬が、区間 $1$ から区間 $M$ までを順番に走る。
• 馬は 区間 $i$ に入る $\to$ 区間 $i$ を出る $\to$ 区間 $i+1$ に入る $\to$ 区間 $i+1$ を出る$\dots$ を繰り返す。
• 区間は連続しているため、区間 $i$ を出てから区間 $i+1$ に入るまでの順位変動は無いものとして良い。
• どの $2$ 頭の馬も、各区間へ入る瞬間と各区間から出る瞬間、同着ではない。
• 区間 $1$ に入る馬の順番は 馬 $1,2,\dots ,N$ の順番である。
• 各区間内では $N$ 頭の馬の順位が変動する可能性がある。

ここで、$1\le l\le r\le M$ なる任意の $l,r$ について「レースのおもしろさ」$E_{l,r}$ を以下のように定義します。

レースが始まってから、あなたのもとに $Q$ 個のクエリが順に届きます。クエリのタイプは以下の $3$ 種類です。

各クエリは、それ以前のクエリの情報を基に処理してください。(詳しくは制約やサンプルも確認してください)

• type $1$ : 区間 $D$ に $i$ 番目に入った馬が区間 $D$ を $P_i$ 番目に出たという情報があなたのもとに届く。 このクエリより前の、区間 $D$ に対する情報は無視する。
• type $2$ : 区間 $S$ を出た馬を $1$ 番目から順に全て出力する。
• type $3$ : 区間 $L$ から区間 $R$ までの「レースのおもしろさ」$E_{L,R}$ を出力する。

制約

入力

$NMQ$
$Quer{y}_1$
$⋮$
$Quer{y}_Q$

$Quer{y}_i$ は、以下の $3$ つのいずれかである。

$1D{P}_1\dots P_N$

$2S$

$3LR$

出力

type $2$ の各クエリについては、$1$ 着から $N$ 着までの馬の番号を空白区切りで一行に出力し、改行してください。

type $3$ の各クエリについては、$E_{L,R}$ を一行に出力し、改行してください。

サンプル

3 3 7
1 1 1 3 2
1 2 2 1 3
1 3 2 3 1
2 3
3 1 3
1 2 1 2 3
2 3

2 3 1
4
2 1 3

4 5 10
1 1 3 4 2 1
1 2 1 3 2 4
2 2
1 3 2 3 4 1
3 1 3
1 2 1 2 3 4
1 4 2 1 4 3
2 4
1 5 3 2 4 1
3 1 5

4 1 3 2
6
4 2 1 3
6