Segment Tree Range Maximum Query and Update

You are given an array of n integers and m operations to perform on the array. There are two types of operations:

• Update Operation: Given an index i and a value v, update the array element at index i to v.
• Query Operation: Given indices l and r, find the maximum value in the subarray from index l to r (inclusive). That is, compute \[ \max_{l \leq i \leq r} a_i \]

The array is 1-indexed. Your task is to process all the operations and output the answer for every query operation.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵), representing the number of elements in the array and the number of operations, respectively.

The second line contains n integers representing the initial array elements.

The following m lines each contain three integers, describing an operation in one of the following formats:

• 1 i v for an update operation, which sets the element at index i to v.
• 2 l r for a query operation, which asks for the maximum value in the range from index l to r (inclusive).

Input is to be read from standard input (stdin).

outputFormat

For each query operation, output the maximum value found in the given range. Each answer should be printed on a new line. Output is to be written to standard output (stdout).

## sample

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

7
10
10

</p>