P1003：区间增加、区间最大值

题目描述

给定一个长度为 $N$ 的数组 $a$。 执行 $Q$ 次操作，操作分为两类：

1. 将区间 $[l,r]$ 内的所有元素增加 $x$
2. 查询区间 $[l,r]$ 内所有元素的最大值

输入输出格式

输入

第一行输入两个整数 $N$ 和 $Q$.

第二行输入 $N$ 个整数 $a_1 \sim a_n$.

接下来 $Q$ 行，每行表示一个操作，格式如下：

• $1\ l\ r\ x$ （对应加操作）
• $2\ l\ r$ （对应最大值查询）

输出

对于每一次查询操作，输出一个整数作为结果。

样例

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

5
7
5

数据范围

$1 \le N,Q \le 2\times 10^5$, $-10^9 \le a_i \le 10^9$