011 - N数列

問題

$N$個の要素からなる$N$本の数列$A_1,A_2, ... ,A_N$があり、数列$A_i$の$j$番目の要素を$A_{i,j}$と表す。最初はすべての数列$A_i$について$(A_{i,1},A_{i,2}, ... ,A_{i,N} )=(a_1,a_2, ... ,a_N)$であるとする。 数列$A_1,A_2, ... ,A_N$に対して、以下の３種類の操作が行える。

• 数列$A_y$を数列$A_x$で置き換える。
• 数列$A_x$の$s$番目の要素$A_{x,s}$の値と、数列$A_y$の$t$番目の要素$A_{y,t}$の値を入れ替える。
• 数列$A_x$に対して、$s$番目から$t$番目の要素の総和を出力する。

数列の初期値と操作のリストが与えられたとき、リスト中のすべての操作を順番に行うプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $Q$
$a_1$ $a_2$ ... $a_N$
$query_1$
$query_2$
:
$query_Q$

１行目に数列の本数と要素の数$N$ ($2 \leq N \leq 200,000$)と操作の数$Q$ ($1 \leq Q \leq 200,000$)が与えられる。続く１行に、すべての数列の要素の初期値$a_i$ ($1 \leq a_i \leq 1,000,000,000$)が整数で与えられる。続く$Q$行に、操作のリスト中の$i$番目の操作$query_i$が与えられる。各操作は以下のいずれかの形式で与えられる。

1 $x$ $y$

または

2 $x$ $s$ $y$ $t$

または

3 $x$ $s$ $t$

1 $x$ $y$ は、数列$A_y$ ($1 \leq y \leq N$)を数列$A_x$ ($1 \leq x \leq N$)で置き換える操作を表す。

2 $x$ $s$ $y$ $t$ は、数列$A_x$ ($1 \leq x \leq N$)の$s$ ($1 \leq s \leq N$)番目の要素の値と、数列$A_y$ ($1 \leq y \leq N$)の$t$ ($1 \leq t \leq N$)番目の要素の値を入れ替える操作を表す。

3 $x$ $s$ $t$ は、数列$A_x$ ($1 \leq x \leq N$)に対して、$s$ ($1 \leq s \leq N$)番目から$t$ ($s \leq t \leq N$)番目の要素の総和を出力する操作を表す。この操作は１回以上与えられる。

出力

総和を出力する操作それぞれについて、結果を１行に出力する。

入出力例

入力例１

3 4
1 2 3
3 1 2 3
2 1 2 3 3
1 1 3
3 1 2 3

出力例１

5
6

入力例２

3 6
1 2 3
3 3 1 3
2 1 1 3 3
1 3 2
3 1 1 3
3 2 1 3
3 3 1 3

出力例２

6
8
4
4