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