Background

不知为何，果老板迷上了辣条，或许一切都是从魏老板那天中午给了果老板一包鱼香脆骨开始。从此果老板走上了一条又菜又爱吃的辣条之路。——《果传》题记。（魏老板加的）

作为辣条爱好者，果老板每天晚上回去的时候都要吃一包辣条。

但第一天晚上的辣条实在是太辣了，果老板都没吃完！

Description

魏老板想出了一个方案，他买了一大袋各种各样的辣条，拿出来一个挨一个摆在桌子上，果老板从里面挑一包来吃。

果老板非常害怕辣，希望可以选到不怎么辣的辣条，这样会吃的很爽，但他不知道每一包的辣条的辣度都是多少。

作为资深元老魏老板，他当然清楚每一包辣条吃起来的口感，当然也包括辣度，但魏老板提出了一个条件，果老板每次只可以询问桌子上某个区间内的辣条，魏老板会告诉他这个区间内最辣的辣条的辣度。

果老板挑的实在是太慢了，在这中间，有其他同学也送来辣条，魏老板可以选择桌子上的某一包辣条替换成新送来的辣条。

Format

Input

第一行两个整数 $N$ 和 $K$ ，表示桌子上有 $N$ 包辣条和一共有 $K$ 次事件。

接下来一行有 $N$ 个整数 $a_i$ ，表示每一包辣条的辣度。

接下来有 $K$ 行每行三个整数，表示果老板的提问或者魏老板的替换：

当第一个数 $t$ 为 $0$ 时表示果老板的提问，紧跟着两个整数 $l$ $r$ 表示果老板提问的区间，魏老板会告诉他桌子上第 $l$ 包辣条到第 $r$ 包辣条的辣度的最大值。

当第一个数 $t$ 为 $1$ 时表示魏老板的替换，紧跟着两个数 $x$ $a$表示魏老板会将桌子上的第 $x$ 包辣条替换，新的辣条的辣度为 $a$。

Output

对于每次果老板的提问 $(t = 0)$ ，输出一行一个整数，表示魏老板回答的辣度。

Samples

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

7
5
6