Segment Tree Range Maximum Query

You are given an array of integers and you need to process a series of queries. There are two types of queries:

• Update query: 1 x y which updates the element at index x (1-indexed) to value y.
• Range maximum query: 2 x y which asks for the maximum element in the subarray from index x to y (1-indexed, inclusive on the left and exclusive on the right in our implementation details).

You are required to implement these queries efficiently using a segment tree.

The segment tree is built on an array of size \( n \) and stored in an array of size \(2n\). The leaves are stored in positions \( n \) to \( 2n-1 \), and each internal node at position \( i \) holds the value max(tree[2i], tree[2i+1]).

Process the queries sequentially. For update queries, update the segment tree accordingly. For range maximum queries, output the maximum value in the given range.

inputFormat

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.

The second line contains \( N \) space-separated integers representing the array elements.

The next \( Q \) lines each contain a query in one of the following formats:

• 1 x y: Update the element at index \( x \) (1-indexed) to y.
• 2 x y: Output the maximum element in the range from index \( x \) to \( y \) (1-indexed, inclusive for the left bound and exclusive for the right bound as per implementation, but effectively from \( x \) to \( y \) in problem context).

outputFormat

For each query of type 2, output a single line containing the maximum value found in the specified range.

## sample

5 5
1 5 2 4 3
2 1 3
1 4 10
2 2 5
1 1 20
2 3 3

5
10
2

</p>