题目描述

这是一道线段树经典题。

你需要写一个数据结构（线段树）维护长度为 $ 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 $。

输入格式

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

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

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

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

输出格式

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

样例 1

input

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

output

11
5
16
7
22
10

样例 2

input

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

output

0
-40
3
-27
-40
3

数据范围与提示

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

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