Range Maximum Query with Point Update

You are given an array of (n) integers and are required to process (q) queries on it. There are two types of queries:

1. Update: Given by (1\ x\ y). Update the element at position (x) (1-indexed) to the new value (y).

2. Range Maximum Query: Given by (2\ l\ r). Query the maximum value in the subarray from index (l) to (r) (inclusive). This is equivalent to computing (\max{array[l], array[l+1], \ldots, array[r]}).

It is recommended to use a segment tree for efficient processing of these queries. The queries are executed sequentially, and only the results of the range maximum queries (type 2) should be printed.

inputFormat

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

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

Where:

• \(n\) and \(q\) are integers representing the number of elements and the number of queries, respectively.
• The second line contains \(n\) space-separated integers which form the initial array.
• Each of the next \(q\) lines contains a query in one of the following forms:
  • 1 x y: Update the element at index \(x\) to \(y\) (1-indexed).
  • 2 l r: Output the maximum value in the subarray from index \(l\) to \(r\) (1-indexed).

outputFormat

For each range maximum query (type 2), output the corresponding maximum value on a separate line to the standard output (stdout).

## sample

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

5
10
10

</p>