# 1220. intelligence

One day , sunny’s classmates ask him for help,because they meet a very difficult problem .They want to calculate the highest number in a given interval ,and it may change some number.how do you solve it.

### 输入格式

First input two numbers n (n<=200000)and m(m<=5000),n stand for the interval’s range from 1 to n,m stand for the time of operation.

The second line input n numbers stand for the initialization number in n place

Then following m line ,if the first is a letter Q ,stand for asking, then follow two numbers A,B ,mean ask the highest number in the interval from A to B.Out put the number in a line.

if it is a letter U , and follow two numbers A B(A<=B),mean you must change the position A’s number to B.Output nothing.

### 输出格式

For each Q ,output the highestnumber in the given interval [A,B].

### 样例

Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Output
5
6
5
9


12 人解决，32 人已尝试。

21 份提交通过，共有 161 份提交。

7.2 EMB 奖励。