[Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?

题目背景

今天真是多谢你了 让我体验了许多美好 我留下了如同美梦一般的回忆 不过时间到了 最后我还想拜托你一件事 希望你可以把我忘掉 ![](https://cdn.luogu.com.cn/upload/pic/13170.png) 在自己消失之前 心怀不想消失的愿望 希望让某个人记住我 希望能留下羁绊 我这么希望着,又有什么不可以的吗 ![](https://cdn.luogu.com.cn/upload/pic/13171.png) 香香甜甜的,真好闻 看起来很好吃 ![](https://cdn.luogu.com.cn/upload/pic/13173.png) 我遵守了... 约...约定 我非常...非常努力哦... ![](https://cdn.luogu.com.cn/upload/pic/13172.png) 欢迎回来,珂朵莉

题目描述

珂朵莉给了你一个长为 $n$ 的序列 $a$,有 $m$ 次操作。 1. 把区间 $[l,r]$ 内所有数都加上 $x$。 2. 查询区间 $[l,r]$ 内的最大子段和,可以不选数。

输入输出格式

输入格式


第一行两个整数 $n,m$。 第二行 $n$ 个整数表示序列 $a$。 后面 $m$ 行: - `1 l r x`:把区间 $[l,r]$ 内所有数加上 $x$。 - `2 l r`:查询区间 $[l,r]$ 的最大子段和。

输出格式


对于每个询问,输出一个数表示答案。

输入输出样例

输入样例 #1

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

输出样例 #1

0
3
2

输入样例 #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

输出样例 #2

6
3
0

说明

Idea:nzhtl1477,Solution:ccz181078,Code:nzhtl1477&ccz181078&mrsrz,Data:nzhtl1477&mrsrz $1 \le n , m \le 10^5$,$| a_i | \leq 10^9$,$|x|\leq 10^9$。 **保证任意时刻 $|a_i|\leq 2\times 10^9$。** By nzhtl1477 & ccz181078