Description

这是一道线段树经典题。

你需要写一个数据结构（线段树）维护长度为 $n ​$ 的三个序列 $A,B,C ​$，下标为 $1\sim n ​$，支持：

• 对于 $i\in[l,r]$，令 $A_i\leftarrow\min (A_i,x)$ 。

• 对于 $i\in [l,r]$，令 $A_i\leftarrow A_i+x$。

• 求 $\sum_{i=l}^r A_i ​$。

• 求 $\sum_{i=l}^r B_i$。

• 求 $\max_{i=l}^r C_i$。

每次修改操作后（前两种操作），令 $ B_i\leftarrow B_i+A_i,C_i\leftarrow\max(C_i,A_i) ​$。

初始给定 $A_i$，同时初始 $B_i=0,C_i=A_i$。

Input Format

第一行两个正整数 $n,Q$，分别表示序列长度和操作个数。

第二行 $n$ 个整数表示序列 $A_i$。

接下来 $Q$ 行，每行第一个整数表示操作类型编号，其他数字意义同题面：

• 若为类型 $1 ​$，接下来三个整数 $l,r,x ​$。
• 若为类型 $2$，接下来三个整数 $l,r,x$。
• 若为类型 $3 ​$，接下来两个整数 $l,r ​$。
• 若为类型 $4$，接下来两个整数 $l,r$。
• 若为类型 $5$，接下来两个整数 $l,r$。

Output Format

对于每个类型为 $3,4,5 ​$ 的操作，输出一行一个整数表示答案。

Sample

样例输入 1

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

样例输出 1

11
5
16
7
22
10

样例输入 2

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

样例输出 2

0
-40
3
-27
-40
3

Hint

对于 $100\%$ 的数据，$1\leq n,Q\leq 2\times 10^5,|a_i|\leq 10^9$，$1\leq l\leq r\leq n$，数据保证过程中所有相关数值及输出的绝对值均在 long long 范围内。

数据均为随机，但没有梯度。