题目描述

给定长度为$n$的序列$a_i$，以及$m$个操作。 操作一：1 l r x，对于$\forall i\in[l,r]$，$a_i$加上一个数$x$。 操作二：2 l r，询问$\forall i\in [l,r]$，$a_i$的和。 操作三：3 l r，询问$\forall i\in [l,r]$，$a_i$的最大值。

对于操作二和操作三，给出答案。

输入格式

第一行输入两个整数$n,m$； 第二行输入$n$个整数$a_i$； 接下来$m$行，每行输入一个操作，格式如题面所示。

输出格式

输出若干行，对于每个操作二和操作三，按顺序输出询问的答案。

样例输入 #1

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

样例输出 #1

15
6
18

说明/提示

保证$1\leq n,m\leq 10^5,1\leq a_i,x\leq 10^9,1\leq l\leq r\leq n$。