Sequence Update and Range Maximum Query

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

• Type 1: Update the value at position \(i\) to a given value \(x\). The query is represented as: 1 i x.
• Type 2: Query the maximum value in the subarray from index \(l\) to \(r\) (inclusive). The query is represented as: 2 l r.

Note that the indices in the queries are 1-indexed. After processing all queries, output the result of each type 2 query on a new line.

The problem can be formulated using a segment tree. The update and query operations should both be efficient. In particular, if you denote the sequence by \(a_1,a_2,\dots,a_n\), then a type 2 query requires computing \[ \max_{l \leq i \leq r} a_i. \]

inputFormat

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

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

Where:

• n is the number of elements in the sequence and q is the number of queries.
• The next line contains n integers, representing the initial sequence.
• Each of the following q lines represents a query in one of the two forms described above.
</p>

outputFormat

For each type 2 query, print the maximum value in the given range on a new line to stdout.

## sample

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

3
10

</p>