题目描述

《I Hate It》

【I Hate It】单点改值 + 区间最大值查询 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

输入格式

第一行，有两个正整数 n 和 m（0<n≤2×10^5,0<m≤2×10^5 ），分别代表学生的数目和操作的数目。学生 ID 编号分别从 1 编到 n。 第二行包含 n 个整数，代表这 n 个学生的初始成绩，其中第 i 个数代表 ID 为 i 的学生的成绩，保证学生的成绩为 1～10^9 之间的正整数。 接下来有 m 行。每一行有一个字符 c（只取 Q 或 U），和两个正整数 a，b。 当 c 为 Q 的时候，表示这是一条询问操作，它询问 ID 从 a 到 b（包括 a,b） 的学生当中，成绩最高的是多少； 当 c 为 U 的时候，表示这是一条更新操作，如果当前 a 学生的成绩低于 b，则把 ID 为 a 的学生的成绩更改为 b，否则不改动。

输出格式

对于每一次询问操作输出一行一个整数，表示最高成绩。

样例

输入样例 1

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

输出样例 1

5
6
5
9

输入样例 2

3 3
10 20 30
U 2 15
Q 1 3
U 1 10
Q 1 1

输出样例 2

30

输入样例 3

1 3
5
Q 1 1
U 1 10
Q 1 1

输出样例 3

5
10

输入样例 4

2 5
1 1
U 1 5
U 1 3
U 1 10
Q 1 2

输出样例 4

10
10