Segment Tree: Range Maximum Query and Update

This problem involves implementing a data structure to efficiently process two types of operations on an array:

• Update Operation: Change the array element at position \(x\) to a new value \(y\).
• Query Operation: Find the maximum element in the subarray from index \(x\) to \(y\) (inclusive).

You are required to implement these operations using an appropriate data structure. A segment tree is a commonly used data structure for this type of problem. The update operation can be represented as:

[ \texttt{1 \ x \ y} ]

and the query operation as:

[ \texttt{2 \ x \ y} ]

where indices are 1-based. For each query operation (type 2), output the maximum element in the range \([x, y]\). The number of queries \(Q\) is given and both operations must be processed in the order they appear.

inputFormat

The input is given via standard input (stdin) and has the following format:

N Q
a1 a2 ... aN
query1
query2
...
queryQ

Where:

• \(N\) is the number of elements in the initial array.
• \(Q\) is the number of queries.
• Each query is represented by three integers. For an update query, the query is 1 x y meaning update \(a[x]\) to \(y\). For a range query, the query is 2 x y meaning output the maximum element in the subarray from \(a[x]\) to \(a[y]\) (inclusive).

outputFormat

For each range query (query type 2), output the corresponding maximum value on a new line. The outputs must be written to standard output (stdout) in the order the queries appear.

## sample

5 5
1 2 3 4 5
2 1 5
1 3 10
2 2 4
1 5 6
2 1 5

5
10
10

</p>