You are given a sequence whose length is n, and m operations, each operation is one of the two kinds below:

change : 1 a b change the ath number to b. 1 <= a <= n, |b| < 100000

query : 2 a b query maximum number in the interval [a, b].

There is only one test case.

the first line are the integer n, m. 1 <= n <= 100000, 0 <= m <= 100000.

the seconde line is n numbers in the initial sequence.

the next m lines, each containing one of the two operations memtino above.

for each query operation output a line containing the answer.

5 4
1 2 3 4 5
1 4 7
2 1 5
1 1 -34
2 3 5

7
7