No testdata at current.

Description

给你一个长度为n的数组a，有m次操作，每次给你一个数字op，

• 若op=1，则再输入两个数l，r，请求出a数组区间(l,r)里的最大值。
• 若op=2，则再输入两个数x，k，表示将数组a的第x项修改为k。

Format

Input

第一行两个正整数，n，m。第二行n个整数，表示数组a。后面m行，每行3个正整数。

Output

对于每一次op=1的操作，输出结果。

Samples

5 6
2 4 3 1 5
1 1 5
1 2 4
1 4 4
1 1 2
2 5 0
1 1 5

5
4
1
4
4

Limitation

对于40%的数据，$1≤n,m≤10^3$ 对于100%的数据，$1≤l≤r≤n≤5*10^5，1≤m≤2*10^5$