Sequence Operations: Update and Range Maximum Query

You are given a sequence of n integers: $$a_1, a_2, \ldots, a_n$$. You have to perform m operations on this sequence. There are two types of operations:

• Type 1: Update the sequence at position \(i\) with a new value \(x\). In other words, set \(a_i = x\).
• Type 2: Query the maximum value in the subarray from position \(l\) to \(r\), i.e., compute \(\max(a_l, a_{l+1}, \ldots, a_r)\).

The operations are 1-indexed. Your task is to process all the operations in order and output the result of each operation of type 2.

Input/Output: The input is taken from standard input (stdin) and the output is written to standard output (stdout).

inputFormat

The first line contains two integers (n) and (m), representing the length of the initial sequence and the number of operations respectively. The second line contains (n) integers representing the initial sequence. Each of the following (m) lines describes an operation in one of the following formats:

For an update operation (type 1):

1 i x

For a query operation (type 2):

2 l r

It is guaranteed that the indices are 1-indexed.

outputFormat

For each query operation (type 2), output the maximum value in the specified range on a separate line.## sample

5 4
3 1 4 1 5
2 2 4
1 3 9
2 2 4
2 1 5

4
9
9