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, \ldots, 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