题目背景

他说他解决了经典根号复杂度问题，怕引起轰动所以撤回了.jpg

不过 EntropyIncreaser 确实得到了此题更优的做法。

题目描述

给定一个整数序列 $a$，支持两种操作：

• 1 l r x 表示给区间 $[l,r]$ 中每个数加上 $x$
• 2 l r 表示查询区间 $[l,r]$ 的最大子段和（可以为空）

输入格式

第一行两个正整数 $n,q$，表示序列长度和操作个数。
接下来一行 $n$ 个整数，表示初始的序列 $a$。
接着有 $q$ 行，每行若干个整数，表示一次操作。

输出格式

对于每个 $2$ 操作，输出一行一个整数表示答案。

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

0
3
2

提示

【数据范围】
对于 $20\%$ 的数据，$1\le n,q \le 1000$；
对于 $60\%$ 的数据，$1\le n,q \le 10^5$；
对于 $100\%$ 的数据，$1\le n,q \le 4\times 10^5$，$|a_i| \le 10^9$，$1 \le x \le 10^6$。

Idea：nzhtl1477
Solution：EntropyIncreaser
Code：EntropyIncreaser
Data：NaCly_Fish

请注意常数优化。