在古希腊神话中，人们相信奥林匹斯众神是通过与泰坦巨神之间一场持久的战争获得了他们的力量。

在最近的一些挖掘之后，一个考古团队发现了阐释人们认为这场战争是如何发生的手稿。

奥林匹斯众神的领袖宙斯和泰坦巨神的领袖克洛诺斯，各自挑选了他们最优秀的 $N$ 名士兵进行战斗。

然后，士兵们排成两排，一排只包含奥林匹斯众神，另一排只包含泰坦巨神，使得每位士兵都恰好面对一位对手。

在战斗开始时，每对士兵 $i$ ($1 \le i \le N$) 都有一个分数 $A_i$，这是一个整数，代表战争的哪一方占有优势。正数代表宙斯和奥林匹斯众神占优，负数代表泰坦巨神占优。

在战争期间，发生了 $Q$ 个事件。这些事件可能分为两种：要么是由于宙斯和克洛诺斯的行动（例如，用闪电劈开大山）导致所有对士兵的相对力量发生了变化，要么是宙斯对其军队的优势进行了战略评估。

在第一种情况下，同一个整数 $X$ 被加到了每一个 $A_i$ 上。如果 $X$ 大于 $0$，这意味着宙斯增强了他军队的力量；而负值意味着泰坦巨神增强了他们的力量；值为 $0$ 则意味着没有任何变化。

在第二种情况下，宙斯关注士兵的一个区间 $[L, R]$ ($1 \le L \le R \le N$)：他考虑了所有可能的子区间，即所有满足 $L \le l \le r \le R$ 的 $l, r$，并计算了每个子区间的和 $A_l + A_{l+1} + \dots + A_r$。他计算了所有可能子区间中这些和的最大值 $M$，并宣布 $V = \max(M, 0)$ 为他军队优势的战略评估值。

显然，宙斯的智慧使他能够瞬间计算出这些值，但遗憾的是，他没有在任何地方记录它们。

你作为一名文献学家的任务是提供宙斯在战争期间做出的所有战略评估的值。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $Q$。第二行包含 $N$ 个空格分隔的整数 $A_i$，代表战争开始时的状态。接下来的 $Q$ 行按时间顺序描述战争中的事件。每个事件为以下之一：

• 单词 STRENGTH，后跟一个空格和一个整数 $X$，表示军队的力量发生了变化。
• 单词 ASSESS，后跟空格分隔的整数 $L$ 和 $R$，表示宙斯通过关注区间 $[L, R]$ ($1 \le L \le R \le N$) 对其军队的优势进行了战略评估。

输出格式

对于宙斯每次对其军队优势进行战略评估，按照它们在输入中出现的顺序，你必须输出一行，包含每次评估的值 $V$。

数据范围

• $1 \le N \le 3 \times 10^5$
• $1 \le Q \le 3 \times 10^5$
• 对于 $i = 1, \dots, N$，$-10^9 \le A_i \le 10^9$。
• 所有整数 $X$ 均在 $-10^9$ 到 $10^9$ 之间（含端点）。
• 在战争期间的任何时候，对于所有 $i = 1, \dots, N$，$-2 \times 10^9 \le A_i \le 2 \times 10^9$ 均成立。

样例

输入样例 1

4 6
1 -2 3 4
ASSESS 1 4
ASSESS 1 2
ASSESS 2 2
STRENGTH 2
ASSESS 1 4
ASSESS 1 2

输出样例 1

7
1
0
14
3