問題文

長さ $N$ の数列 $X={x_1,x_2,...,x_N}$ があります．この列に $Q$ 回のクエリ操作を行うことを考えます．クエリ操作は$3$ 種類あり，以下の通りです．

• 1 a b v ― 数列 $X$ の区間 \[a,b\] に一様に値 $v$ を加える．
• 2 a b c d ― 数列 $X$ の区間 \[a,b\] を，クエリが呼ばれた時点での区間 \[c,d\] の値に書き換える．$b-a=d-c$ が保障されている．より厳密には，このクエリによって得られる数列を $X'$ とおくと，$X'_{a}=X_c$，$X'_{a+1}=X_{c+1}$，…，$X'_{b}=X_{d}$ となる．\[a,b\] に含まれない $j$ について，$X'_j=X_j$ となる．
• 3 a b ― 数列 $X$ の区間 \[a,b\] に含まれる値の総和を求める．

あなたは，このようなクエリを順番に処理するプログラムを書かなくてはなりません．

入力

入力は以下の形式で標準入力から与えられる．

$N$ $Q$ $x_1$ $x_2$ … $x_N$ $Query_1$ $Query_2$ : $Query_Q$

• $1$ 行目には，数列 $X$ の長さを表す整数 $N (1 ≦ N ≦ 2×10^5)$ とクエリの数を表す整数 $Q (1 ≦ Q ≦ 2×10^5)$ が与えられる．
• $2$ 行目には，数列 $X$ の $i$ 番目の要素の値 $x_i (-10^6 ≦ x_i ≦ 10^6)$ がスペース区切りで $N$ 個与えられる．
• $3$ 行目から $Q$ 行，問題文中で説明したクエリが，1 a b v， 2 a b c d もしくは 3 a b の形式で与えられる．$\-10^6 ≦ v ≦ 10^6$，$1 ≦ a ≦ b ≦ N，1 ≦ c ≦ d ≦ N，b-a = d-c$であることが保障されている．

出力

3 a b の形式のクエリに対し，与えられた順番に答えを出力せよ．出力毎に改行を行うこと．

入力例1

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

出力例1

15
9
20

• $1$ つ目のクエリは，\[1,5\] の総和を出力するクエリであり，$1+2+3+4+5=15$ を出力します．
• $2$ つ目のクエリは，\[1,3\] に一様に $1$ を足すクエリであり，この操作を行った後，$X={2,3,4,4,5}$ となります．
• $3$ つ目のクエリは，\[1,3\] の総和を求めるクエリであり，$2+3+4=9$ を出力します．
• $4$ つ目のクエリは，\[2,4\] の値を \[1,3\] にコピーするクエリであり，この操作を行った後，$X={3,4,4,4,5}$ となります．
• $5$ つ目のクエリは，\[1,5\] の総和を求めるクエリであり，$3+4+4+4+5=20$ を出力します．

入力例2

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

出力例2

-20
-8
-18
1
-29
-36
-78
-18
-50
-86
-38