You are given an array of $N$ elements. Support the following two operations:

• UPDATE i v - Set the element at index i to v.
• QUERY l r - Output the maximum element of the subarray bounded by l and r.

Constraints

$1 \le N, Q \le 10^6$

$1 \le i, l, r \le N$

The array will only contain positive integers between $1$ and $10^9$ inclusive.

There will be at least one QUERY operation.

Input Specification

The first line contains two integers, $N$ and $Q$.

The next line contains $N$ integers, the elements of the array in order.

The next $Q$ lines contain one of the lines as formatted above.

Output Specification

For each QUERY, output the maximum such element.

Sample Input

3 3
1 2 3
QUERY 1 3
UPDATE 2 4
QUERY 1 3

Sample Output

3
4