题目描述

给出一个长度为 $n$ 的序列，要求支持如下两种操作：

• $A\ \ l\ \ r\ \ x$ ：将 $[l,r]$ 区间内的所有数加上 $x$ ；

• $Q\ \ l\ \ r$ ： 求 $[l,r]$ 区间的最大连续子段和。

其中，一个区间的最大连续子段和指的是：该区间所有子区间的区间和中的最大值（本题中子区间包括空区间，区间和为 $0$ ）。

输入格式

第一行两个整数 $n$、$m$，表示序列的长度以及操作的数目。
第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示序列中的第 $i$ 个数。
之后的 $m$ 行，每行输入一个操作，含义如题目所述。保证操作为 $\ A\ \ l\ \ r\ \ x\$ 或 $\ Q\ \ l\ \ r\$ 之一。

输出格式

对于每个 $Q$ 操作输出一行一个整数，表示询问区间的最大连续子段和。

样例

5 5
2 -3 0 4 -7
Q 1 2
Q 1 5
A 2 3 2
Q 2 5
Q 1 3

2
4
6
3

第一、二个 $Q$ 操作时序列为 $2,-3,0,4,-7$ ，$[1,2]$ 的最大连续子段和为 $[1,1]$ 的区间和 $2$ ，$[1,5]$ 的最大连续子段和为 $[4,4]$ 的区间和 $4$ ； 第三、四个 $Q$ 操作时序列为 $2,-1,2,4,-7$ ，$[2,5]$ 的最大连续子段和为 $[3,4]$ 的区间和 $6$ ，$[1,3]$ 的最大连续子段和为 $[1,3]$ 的区间和 $3$。

数据范围与提示

对于 $30\%$ 的数据，$n,m\le 300$ ；
对于 $60\%$ 的数据，$n,m\le 1000$ ；
对于 $100\%$ 的数据，$1\le n,m\le 50000,\ |a_i|\le 10^9,\ 1\le x\le 40000,\ 1\le l,r\le n$ 。