今天真是多谢你了

让我体验了许多美好

我留下了如同美梦一般的回忆 不过时间到了

最后我还想拜托你一件事

希望你可以把我忘掉

在自己消失之前

心怀不想消失的愿望

希望让某个人记住我

希望能留下羁绊

我这么希望着，又有什么不可以的吗

香香甜甜的，真好闻

看起来很好吃

我遵守了...

约...约定

我非常...非常努力哦...

欢迎回来，珂朵莉

这就是你古SB的题目

珂朵莉给了你一个长为 nn 的序列 aa，有 mm 次操作。

1. 把区间 [l,r] 内所有数都加上 xx。
2. 查询区间 [l,r]内的最大子段和，可以不选数

shurugeshi

第一行两个整数 n,mn,m。

第二行 nn 个整数表示序列 aa。

后面 mm 行：

1 l r x：把区间 [l,r][l,r] 内所有数加上 xx。
2 l r：查询区间 [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

输出

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

输出

6
3
0