题目描述

给出一个长度为 $ 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 $ 操作输出一行一个整数，表示询问区间的最大连续子段和。

样例

input

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

output

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$ 。