1378 - Sequence again

Time Limit: 1s Memory Limit: 128MB

Submissions: 714 Solved: 148
Description

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].

Input

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.

Output

for each query operation output a line containing the answer.

Sample Input
5 4
1 2 3 4 5
1 4 7
2 1 5
1 1 -34
2 3 5
Sample Output
7
7
Hint

Source