P15147 [SWERC 2024] Titanomachy

In ancient Greek mythology, it is believed that the Olympian gods acquired their power from a long lasting war with the Titans. After some recent excavations, an archaeological team found manuscripts explaining how people thought this war happened. Zeus, the leader of the Olympian gods, and Kronos, the leader of the titans, each picked their best $N$ soldiers in order to fight. Then, the soldiers arranged themselves in two rows, one row containing only the Olympian gods, and the other containing the Titans, such that each soldier faced exactly one opponent. At the beginning of the battle, each such pair $i$ ($1 \le i \le N$) of soldiers had a score, $A_i$, which is an integer representing which side of the war had the advantage. A positive number represented an advantage for Zeus and the Olympian gods, a negative number an advantage for the Titans. During the war, $Q$ events occurred. These events could be of two kinds: either the relative strength of all pairs of soldiers changed due to the actions of Zeus and Kronos (for example, breaking down mountains with lightning), or Zeus conducted a strategic assessment of his army’s advantage. In the first case, the same integer $X$ got added to every single $A_i$. If $X$ was greater than 0, it meant that Zeus increased the strength of his army, while a negative value meant that the Titans increased their strength, and a value of 0 meant that nothing changed. In the second case, Zeus focused on an interval $[L, R]$ of soldiers ($1 \le L \le R \le N$): he considered every possible subinterval, that is, all $l, r$ such that $L \le l \le r \le R$, and computed the sum $A_l + A_{l+1} + \cdots + A_r$ for each of them. He computed the maximum value $M$ of such sums over all possible subintervals, and declared that $V = \max(M, 0)$ was the strategic assessment of his army’s advantage. Obviously, Zeus’s wisdom allowed him to compute such values instantaneously, but unfortunately, he did not record them anywhere. Your task as a philologist is to provide the values of all the strategic assessments made by Zeus during the war.

The first line of the input contains two space-separated integers $N$ and $Q$. The second line contains $N$ space-separated integers $A_i$, representing the state at the beginning of the war. The following $Q$ lines describe the events of the war, in chronological order. Each of them is either: - The word **STRENGTH**, followed by a space and an integer $X$, meaning that the strength of an army changed. - The word **ASSESS** followed by space-separated integers $L$ and $R$, meaning that Zeus made a strategic assessment of his army’s advantage by focusing on the interval $[L, R]$ ($1 \le L \le R \le N$).

For every time Zeus made a strategic assessment of his army’s advantage, and in the order they appear in the input, you must output one line with the value $V$ of each assessment.

### Limits - $1 \le N \le 3 \times 10^5$ - $1 \le Q \le 3 \times 10^5$ - $-10^9 \le A_i \le 10^9$ for $i = 1, \dots, N$. - All $X$ integers are between $-10^9$ and $10^9$, inclusive. - At all times during the war, $-2 \times 10^9 \le A_i \le 2 \times 10^9$ for all $i = 1, \dots, N$ holds true.