Range Maximum Query with Updates

You are given an array of ( n ) integers, initially all zero. Your task is to process ( q ) queries of two types:

1. Update Query: Change the value at a given index. The query is given in the form: 0 i x, which means set the ( i^{th} ) element to ( x ) (( 1 \leq i \leq n )).
2. Range Maximum Query: Find the maximum value in the subarray from index ( l ) to ( r ) (inclusive). The query is given in the form: 1 l r.

It is guaranteed that the update and query indices satisfy ( 1 \leq i, l, r \leq n ) and ( l \leq r ).

The solution is expected to handle each query efficiently in ( O(\log n) ) time per query by using a segment tree data structure.

Note: All indices in the queries are 1-indexed.

inputFormat

The first line contains two integers ( n ) (the number of elements) and ( q ) (the number of queries). The following ( q ) lines each contain a query in one of the following forms:

• For an update query: 0 i x indicating an update of the ( i^{th} ) element to value ( x ).
• For a range maximum query: 1 l r asking for the maximum value in the subarray from index ( l ) to ( r ).

All input is read from standard input (stdin).

outputFormat

For each range maximum query (query type 1), output the result on a new line. The outputs should be printed to standard output (stdout) in the order the queries appear.## sample

5 4
0 1 5
0 3 7
1 1 4
1 2 5

7
7