省隊選拔結束之後，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$。