Bakery System Query Problem

You are tasked with implementing a system to handle queries on the popularity rankings of a bakery's products. Initially, the bakery has N different items, each with a given popularity rank. You will be given Q queries. There are two types of queries:

• Type 1 (Update): This query is denoted as 1 X Y and instructs you to update the rank of the X-th product to Y.
• Type 2 (Query): This query is denoted as 2 L R and asks for the maximum popularity in the range between indices L and R (inclusive). In mathematical notation, given an array A, the answer is $$\max_{i=L}^{R} A_i.$$

You are required to process the queries in the order given. For each query of type 2, output the result on a new line.

The underlying data structure that efficiently manages these operations is a segment tree.

inputFormat

The first line contains two integers N and Q separated by a space, representing the number of bakery items and the number of queries, respectively.

The second line contains N integers, representing the initial popularity ranks of the bakery items.

The next Q lines each contain a query in one of the following formats:

• 1 X Y for an update operation (change the X-th item's rank to Y).
• 2 L R for a range maximum query (find the maximum among items indexed from L to R inclusive).

Note: The array uses 1-indexing.

outputFormat

For each query of type 2, output the maximum popularity rank on a separate line in the order they appear in the input.

## sample

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

9
10

</p>