Range Maximum Query with Updates using Segment Trees

You are given an array of integers and a sequence of queries. There are two types of queries:

1. Update Query: Change the element at a given position to a specified value. The position is given in 1-indexed format.

2. Range Maximum Query: Given a range [l, r] (1-indexed, inclusive), output the maximum element in that subarray.

You are encouraged to solve this problem efficiently by using a segment tree. In a segment tree, each node represents a segment of the array, and the maximum of that segment is stored. For a range query, the final answer is given by (\max_{l \leq i \leq r} a_i).

Your task is to process all queries and output the results of the range maximum queries to standard output.

inputFormat

The input is given via standard input in the following format:

• The first line contains two integers, n and q, where n is the number of elements in the array and q is the number of queries.
• The second line contains n space-separated integers indicating the initial array.
• This is followed by q lines, each describing a query in one of the following formats:
  • For an update query, the line will be: "1 x y", meaning update the element at index x (1-indexed) to y.
  • For a range maximum query, the line will be: "2 l r", meaning query the maximum value in the subarray from index l to r (inclusive, 1-indexed).

outputFormat

For each range maximum query (queries starting with 2), output a single line containing the maximum value found within the specified range.## sample

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

5
10