Product Ratings Range Queries

You are given an array of product ratings. You need to perform queries on the product ratings using a segment tree to support range maximum queries and point updates. For an update query, update the rating of a product at a given index. For a range query, report the 1-indexed position of the product with the highest rating in the range. If two products have the same rating, choose the one with the smaller index.

The underlying data structure is a segment tree. In a leaf node, store a tuple (rating, index). In an internal node, store the tuple with the maximum rating. In case of ties, the tuple with the smaller index is chosen.

The queries are provided in the following format:

• 1 idx value: update the rating of the product at position idx to value.
• 2 L R: query the subarray from L to R (both inclusive) and return the index (1-indexed) of the product with the highest rating.

All indices in the queries are given using 1-indexing, and you should convert them to 0-indexing for internal processing.

The solution should read input from standard input (stdin) and print the resulting outputs to standard output (stdout), with each query answer on a new line.

inputFormat

The first line contains two integers N and Q, representing the number of products and the number of queries, respectively.

The second line contains N integers, representing the initial ratings of the products.

The next Q lines each contain a query. A query is either:

• "1 idx value" for an update query (update the rating at position idx to value), or
• "2 L R" for a range query (find the product with the highest rating between indices L and R inclusive).

outputFormat

For each range query (queries starting with 2), output the 1-indexed position of the product with the highest rating in the specified range. Each answer should be printed on a separate line.

## sample

5 6
10 20 30 40 50
2 1 5
1 3 25
2 1 3
1 5 45
2 4 5
2 1 5

5
3
5
5

</p>