Range Maximum Query and Update Operations

You are given a sequence of n integers and q queries. There are two types of queries:

• Type 1: 1 pos val - Update the element at position \( pos \) to \( val \).
• Type 2: 2 L R - Output the maximum value in the subarray from index \( L \) to \( R \) (inclusive).

The elements are 1-indexed. After processing all the queries, output the result of each type 2 query on a new line.

Note: To solve this problem efficiently, you might want to use a Segment Tree data structure. The key operation used in the segment tree is defined by the following formula:

\( seg[i] = \max(seg[2i], seg[2i+1]) \)

inputFormat

The input is given in the following format from stdin:

 n q
 a1 a2 ... an
 query1
 query2
 ...
 queryq

Where:

• n is the number of elements in the array.
• q is the number of queries.
• The next line contains n integers representing the array.
• Each of the following q lines represents a query. For a query, if the first integer is 1 then it is an update operation followed by pos and val. If it is 2 then it is a range maximum query followed by L and R.

All indices are 1-indexed.

outputFormat

For each query of type 2, output the maximum value found in the given range on a separate line to stdout in the order the queries appear.

## sample

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

5
7
7

</p>