Background

Many schools have a habit of making comparisons. Teachers often ask, among students from some ID to another, what the highest score is. This annoys many students.

Problem 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