Copy and Sum

長さ$N$の数列Aと数列Bがある。AとBの$i$番目の要素をそれぞれ$a_i$と$b_i$で表す。ただし、$i$は$1$から$N$までの整数である。これらの数列に対して以下の操作を行う。

• copy($x$, $y$, $z$) : $a_x, a_{x+1}, ..., a_{x+z-1}$の値をそれぞれ、$b_y, b_{y+1}, ..., b_{y+z-1}$の値に置き換える。
• sum($p$, $q$) : $a_p + a_{p+1} + ... + a_q$の値を出力する。

数列A，Bと、いくつかの操作が与えられるとき、操作sumの結果を出力するプログラムを作成せよ。

入力

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

$N$ $M$
$a_1$ $a_2$ ... $a_N$
$b_1$ $b_2$ ... $b_N$
$op_1$
$op_2$
:
$op_M$

１行目に数列の長さ$N$ ($1 \leq N \leq 200,000$)と操作の数$M$ ($1 \leq M \leq 200,000$)が与えられる。続く１行に数列Aの$i$番目の要素$a_i$ ($0 \leq a_i \leq 1,000,000,000$)が整数で与えられる。続く１行に数列Bの$i$番目の要素$b_i$ ($0 \leq bi \leq 1,000,000,000$)が整数で与えられる。続く$M$行に、操作を示す情報$op_i$が与えられる。各$op_i$は以下のいずれかの形式で与えられる。

0 $x$ $y$ $z$

または

1 $p$ $q$

最初の文字が0の場合、操作copy($x$, $y$, $z$)を行うことを示す。ただし、$1 \leq x,y \leq N, 1 \leq z,$ max$(x,y)+z-1 \leq N$である。max$(x,y)$は$x$,$y$のうち大きい方を表す。最初の文字が1の場合、操作sum($p$, $q$)を行うことを示す。ただし、$1 \leq p \leq q \leq N$である。入力には、操作sumが１回以上与えられる。

出力

操作sumが与えられるごとに、操作sumの結果を１行に出力する。

入出力例

入力例１

5 5
1 3 5 7 9
2 4 6 8 10
1 1 3
1 4 5
0 4 1 2
1 1 3
1 4 5

出力例１

9
16
9
6

入力例２

6 5
1 2 3 4 5 6
2 4 8 16 32 64
1 1 6
0 1 4 3
1 1 6
0 3 1 3
1 1 6

出力例２

21
127
68

 

---