Comet OJ

C1553 [Ynoi]2018-B

内存限制：256 MB 时间限制：3000 ms

题目描述

珂朵莉给了你一个长为 $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 \le n , m \le 100000 , | a_i | \le 2000000000 , 0 \le x \le 1000000$

输出

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

样例

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

提示