Range Query Array Challenge

You are given an array of integers and are required to process a series of queries on the array. There are three types of operations:

• Update (denoted by U i v): Update the value at index \(i\) (0-indexed) to \(v\).
• Sum Query (denoted by S i j): Compute the sum of the elements between indices \(i\) and \(j\) (inclusive). That is, compute \(\sum_{k=i}^{j} a[k]\).
• Max Query (denoted by M i j): Find the maximum element in the subarray from index \(i\) to \(j\) (inclusive). In mathematical notation, compute \(\max{\{a[i],a[i+1],\dots,a[j]\}}\).

You need to design a data structure that supports these operations efficiently. It is recommended to use segment trees, but any solution that meets the requirements and passes the tests is acceptable.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

1. The first line contains two integers \(N\) and \(Q\), where \(N\) is the number of elements in the array and \(Q\) is the number of queries.
2. The second line contains \(N\) integers representing the initial array.
3. The following \(Q\) lines each describe a query in one of the following formats:
   • U i v: Update the element at index \(i\) (0-indexed) to value \(v\).
   • S i j: Query the sum of the subarray from index \(i\) to \(j\) (inclusive).
   • M i j: Query the maximum value in the subarray from index \(i\) to \(j\) (inclusive).

outputFormat

For each query of type S (sum query) and M (max query), output the corresponding result on a separate line to standard output (stdout). There is no output for update queries.

## sample

5 5
1 2 3 4 5
S 1 3
M 0 2
U 2 10
S 1 3
M 1 4

9
3
16
10

</p>