Sequence again

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.