Manage Contest Participants

You are given an array of integers representing the scores of contest participants. You need to process a series of queries on this array. There are two types of queries:

• Update Query (Type 1): Update the score of a participant. The query is given in the format: 1 i x where i (1-indexed) is the participant's index and x is the new score.
• Range Query (Type 2): Find the maximum score in a subarray. The query is given in the format: 2 l r where l and r (1-indexed, inclusive for l and exclusive for r in our implementation) specify the range. In mathematical notation, if the array is represented as \( A[1..n] \), then for a range query, you are required to output \( \max_{l \leq i \leq r} A[i] \). Note that our implementation uses 0-indexing internally.

It is recommended to use a segment tree for efficient processing. The segment tree is built such that each internal node stores the maximum of its two children. When a participant's score is updated, the corresponding leaf and its ancestor nodes are updated accordingly.

inputFormat

The input is read from standard input (stdin) and consists of:

1. The first line contains two integers \( n \) and \( q \) \( (1 \leq n, q \leq 10^5) \), representing the number of participants and the number of queries.
2. The second line contains \( n \) integers \( A[1], A[2], \ldots, A[n] \), where \( A[i] \) represents the score of the \( i^{th} \) participant.
3. The following \( q \) lines each represent a query in one of the following formats:
   • "1 i x" for an update operation, where \( i \) is the 1-indexed participant index and \( x \) is the new score.
   • "2 l r" for a range maximum query, where \( l \) and \( r \) are the bounds (1-indexed). The answer to this query is the maximum score among participants from index \( l \) to \( r \) (inclusive).

outputFormat

For each range query (Type 2), output the maximum score in the specified range on a new line. There is no output for update queries (Type 1).

## sample

5 3
10 20 15 30 25
2 1 5
1 3 35
2 3 5

30
35

</p>