省代表選考の後、White は長い失意の中に沈んでいました。自分の結果に何の希望も見出せなかったのです。それでも White は NOI 前の最後のトレーニングを続けました。通常の練習に加え、彼女はこれまでの OI 人生で学ぶ機会のなかった分野の探求も始めました——別れを告げる前に、もう後悔を残さないことを願って。

雑念を振り払い、White は目の前にある一問の素朴で退屈なデータ構造の問題にふと意識を集中させました——

White は $n$ 個の整数からなる数列 $a_1, a_2, \dots, a_n$ を持っています。彼女はこの数列に対して $q$ 回の操作を行います。各操作は以下の三種類のいずれかです：

• 1 l r v — 区間 $[l, r]$ 内の各要素に $v$ を加算する。
• 2 l r v — 区間 $[l, r]$ 内の各要素に $v$ を代入する。
• 3 l r — $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ を $2^{64}$ で割った余りを求める。

あなたの仕事は、すべての操作をシミュレートし、すべてのクエリの結果を出力することです。

入力

入力の最初の行には、要素数と操作回数を表す二つの整数 $n, q$（$1 \le n, q \le 2 \times 10^5$）が与えられます。

二行目には、初期要素を表す $n$ 個の整数 $a_1, a_2, \cdots, a_n$（$0 \le a_i \le 10^9$）が与えられます。

続く $q$ 行のそれぞれは、以下の三つの形式のいずれかで操作を表します：

• 1 l r v（$1 \le l \le r \le n, -10^9 \le v \le 10^9$）：加算操作を表す。
• 2 l r v（$1 \le l \le r \le n, 1 \le v \le 10^9$）：代入操作を表す。
• 3 l r（$1 \le l \le r \le n$）：クエリ操作を表す。

全過程を通じて、各 $1 \le i \le n$ について常に $0 \le a_i \le 10^9$ が成り立つことが保証されます。

出力

各クエリ操作について、クエリの結果を $2^{64}$ で割った余りを表す整数を一行に出力してください。

入出力例

入力

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

出力

35
39
40
34
177
120

入力

10 20
1 2 3 4 5 6 7 8 9 10
1 1 10 1
3 1 5
3 2 9
3 8 10
1 2 5 10
3 1 5
3 2 9
3 8 10
1 5 9 -5
3 1 5
3 2 9
3 8 10
1 2 5 -10
3 1 5
3 2 9
3 8 10
1 5 9 5
3 1 5
3 2 9
3 8 10

出力

40
156
270
120
1202
270
118
831
80
33
61
80
40
156
270

注記

最初のテストケースにおいて：

元の数列は 2 3 5 4 1 です。三回目の操作の後、2 3 2 2 1 となり、六回目の操作の後、7 8 7 7 6 となります。

最初のクエリに対する答えは $\sum_{i=1}^5 (\min_{j=1}^i a_j) \times (\max_{j=1}^i a_j) = 2 \times 2 + 2 \times 3 + 2 \times 5 + 2 \times 5 + 1 \times 5 = 35$ です。

二番目のクエリに対する答えは $\sum_{i=2}^4 (\min_{j=2}^i a_j) \times (\max_{j=2}^i a_j) = 3 \times 3 + 3 \times 5 + 3 \times 5 = 39$ です。