Dynamic Array Query Processing

You are given an array of integers of size \(n\) and a sequence of \(q\) queries. There are two types of queries:

• Type 1: Update the value at a given index. The query is presented as 1 x y, which means update the element at position \(x\) (1-indexed) to the value \(y\).
• Type 2: Query for the maximum value in a subarray. The query is presented as 2 l r, which means find the maximum value in the subarray from index \(l\) to \(r\) (1-indexed and inclusive).

Hint: An efficient way to solve this problem is by using a segment tree. The segment tree supports both point updates and range maximum queries in \(O(\log n)\) time.

Input indexing: All indices in the queries are 1-indexed.

inputFormat

The input is provided via standard input and is formatted as follows:

1. The first line contains two integers \(n\) and \(q\) — the number of elements in the array and the number of queries.
2. The second line contains \(n\) space-separated integers representing the array.
3. The next \(q\) lines each contain three integers. For a type 1 query, the line is in the format: 1 x y. For a type 2 query, the line is in the format: 2 l r.

outputFormat

For each query of type 2, print the maximum value in the specified subarray on a new line.

## sample

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

5
10
10

</p>