Taco Query Processor

You are given a sequence of n integers and are asked to process m queries on the sequence. There are two types of queries:

• Update Query: Formatted as \(1\ x\ y\). This updates the \(x\)-th element of the sequence to \(y\).
• Range Maximum Query: Formatted as \(2\ l\ r\). This asks for the maximum value in the subarray from index \(l\) to \(r\) (inclusive).

Indices are 1-indexed. Use efficient methods (for example, a segment tree) to process the queries swiftly. For each range maximum query, output the resulting maximum value on a separate line.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (n) and (m) — the number of elements in the sequence and the number of queries, respectively. The second line contains (n) space-separated integers representing the sequence. The next (m) lines each contain a query in one of the following forms:

1 x y

or

2 l r

where the first form updates the value at index (x) to (y) and the second form requests the maximum in the subarray from index (l) to (r).

outputFormat

For each range maximum query (queries of type 2), output the maximum value found in the specified range on a separate line to standard output (stdout).## sample

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

3
10
7