Segment Tree Maximum Query

In this problem, you are given a sequence of $n$ integers and $q$ queries. There are two types of queries:

1. Update query: Given in the format 1 i x, update the value at position $i$ (1-indexed) in the array to $x$.
2. Query query: Given in the format `2 l r$, output the maximum value in the subarray from index $l$to$r$ (inclusive).

You are required to efficiently process these queries. A typical solution is to use a segment tree data structure which allows both update and maximum range query in $O(\log n)$ time. The segment tree is constructed using the formula

for non-leaf nodes. Please note that the array indices in the input are 1-indexed, so be sure to convert them appropriately when implementing your solution.

inputFormat

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

• The first line contains two integers $n$ and $q$, representing the number of elements in the sequence and the number of queries, respectively.
• The second line contains $n$ integers, the initial elements of the sequence.
• Each of the next $q$ lines contains three integers. If the first integer is $1$, the line represents an update operation in the form 1 i x. If the first integer is $2$, the line represents a range query in the form 2 l r.

outputFormat

For each query of type 2, output the maximum value in the subarray from index $l$ to $r$ on a separate line to standard output.## sample

5 5
1 2 3 4 5
2 1 3
1 2 10
2 1 3
2 2 5
1 4 7

3
10
10