题目背景

很多学校流行一种比较的习惯，老师们喜欢询问从某位同学到另一位同学之间，成绩最高的是多少。这让很多同学感到厌烦。

题目描述

不管同学们是否喜欢，现在需要你按照老师的要求，编写一个程序来处理成绩的查询与更新操作。

给定 $n$ 位同学的初始成绩，你需要处理 $m$ 条操作，操作分为两种：

• 询问：查询编号在 $a$ 到 $b$（含 $a, b$）之间的同学中，成绩最高的值。
• 更新：若编号为 $a$ 的同学当前成绩低于 $b$，则将其成绩更改为 $b$，否则不做修改。

输入格式

第一行两个正整数 $n$ 和 $m$（$0 \lt n \le 2 \times 10^5$，$0 \lt m \le 2 \times 10^5$），分别表示学生人数和操作条数。学生编号从 $1$ 到 $n$。

第二行 $n$ 个正整数，第 $i$ 个数表示编号为 $i$ 的同学的初始成绩，保证成绩为 $1 \sim 10^9$ 之间的正整数。

接下来 $m$ 行，每行一个字符 $c$（仅取 Q 或 U）和两个正整数 $a$, $b$：

• 当 $c$ 为 Q 时，表示一次询问，求编号 $a$ 到 $b$（含 $a, b$）之间的最高成绩；
• 当 $c$ 为 U 时，表示一次更新，若编号 $a$ 的同学成绩低于 $b$，则更新为 $b$。

输出格式

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

样例

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

5
6
5
9

提示

数据范围与约定

对于 $100\%$ 的数据，$1 \le n, m \le 2 \times 10^5$，$1 \le$ 成绩 $\le 10^9$。

思路提示

本题可用线段树或树状数组维护区间最大值。