Description

Whether you like it or not, your task is to write a program that simulates the teacher’s queries as required. Of course, the teacher sometimes needs to update a student’s score.

Input Format

The first line contains two positive integers $n$ and $m$ ($0 < n \le 2 \times 10^5, 0 < m \le 2 \times 10^5$), representing the number of students and the number of operations. Student IDs are numbered from $1$ to $n$.

The second line contains $n$ integers, representing the initial scores of these $n$ students. The $i$-th number is the score of the student with ID $i$, and scores are guaranteed to be positive integers in $1 \sim 10^9$.

The next $m$ lines each contain a character $c$ (only Q or U) and two positive integers $a$ and $b$.

• When $c$ is Q, it is a query operation asking for the maximum score among students whose IDs are from $a$ to $b$ (inclusive).
• When $c$ is U, it is an update operation: if the current score of student $a$ is less than $b$, then set the score of the student with ID $a$ to $b$; otherwise, leave it unchanged.

Output Format

For each query operation, output one line with a single integer representing the maximum score.

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

Hint

Translated by ChatGPT 5