Given an array $A$ of size $N$, support the $Q$ of the following operations:

1. Find the maximum prefix sum of the subarray from index $l$ to index $r$. That is, find the maximum sum of a subarray starting at $l$ and ending in the range $[l,r]$.
2. Update the element at index $i$ to value $x$.

Constraints

$1\le N,Q\le 2\times {10}^5$

$1\le l\le r\le N$

$1\le i\le N$

$-{10}^9\le A_i,x\le {10}^9$

Input Specification

The first line contains $2$ integers $N$ and $Q$.

The second line contains $N$ integers $A_1,A_2,\dots ,A_N$, the initial elements of $A$.

The next $Q$ lines are one of two forms:

1. P l r representing the first operation.
2. U i x representing the second operation.

Output Specification

For each type $1$ operation output one integer on its own line, the answer to that query.

Sample Input

7 5
-1 3 2 -6 5 -6 7
P 2 6
P 5 7
U 4 -3
P 2 6
P 1 1

Sample Output

5
6
7
-1