1446 - Copy&Sum

問題文

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

$\bullet \ copy(x,y,z):a_{x}, a_{x+a}, \ldots, a_{x+z-1}$の値をそれぞれ、$b_{y}, b_{y+1}, \ldots, b_{y+z-1}$の値に置き換える。
$\bullet \ sum(p,q):a_{p} + a_{p+1} + \ldots + a_{q}$の値を出力する。

課題

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

入力

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

$N \ M$
$a_{1} \ a_{2} \ \ldots \ a_{N}$
$b_{1} \ b_{2} \ \ldots \ b_{N}$
$op_{1}$
$op_{2}$
$\vdots$
$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)$が整数で与えらえる。
続く1行に数列$B$の$i$番目の要素$b_{i}\ (0 \leq b_{i} \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$が1回以上与えられる。

出力

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

入出力例

入力例1

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

出力例1

9
16
9
6

入力例2

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

出力例2

21
127
68