Problem Statement

長さ $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]$ に含まれる値の総和を求める．

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

Input

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

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$であることが保障されている．

Output

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