Taco: Segment Tree Maximum Query

You are given an array of integers. Your task is to process a series of queries on the array. There are two types of queries:

• U x y: Update the element at position \(x\) (1-indexed) to \(y\).
• Q l r: Query the maximum value in the subarray from position \(l\) to \(r\) (inclusive, 1-indexed).

You are required to implement these operations efficiently using a segment tree. The segment tree is defined using the recurrence formula: $$T[i] = \max(T[2i],\; T[2i+1])$$ where the leaves represent the initial array values.

For each query of type Q, output the result on a separate line.

inputFormat

The input is read from stdin and has the following format:

n q
arr[1] arr[2] ... arr[n]
query_1
query_2
...
query_q

Where the first line contains two integers (n) and (q), representing the number of array elements and the number of queries, respectively. The second line contains (n) space-separated integers representing the array. Each of the following (q) lines contains a query in one of the following forms:

• U x y: Update the element at index \(x\) (1-indexed) to \(y\).
• Q l r: Query the maximum element in the subarray from index \(l\) to \(r\) (inclusive).

outputFormat

The output is written to stdout. For each query of type Q, output the maximum element in the specified subarray on a new line.## sample

5 5
1 2 3 4 5
Q 1 3
U 2 10
Q 1 3
U 3 7
Q 2 5

3
10
10