F. First Problem
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Germán is new to writing programming problems. To get started, he decided to create a simple one (this is the very first problem he has written).

You are given a list of numbers $$$B$$$ of length $$$N$$$, and $$$K$$$ operations that can be of any of the following three types:

  • Q l r — Query the maximum number in the range $$$[l, r]$$$ of the list $$$B$$$.
  • A l r — Add one to every number in the range $$$[l, r]$$$ of the list $$$B$$$.
  • R l r — In the range $$$[l, r]$$$ of the list $$$B$$$, reset to 0 every number that is equal to the global maximum value of the entire list $$$B$$$ (not just the maximum in [$$$l, r$$$]).

Your task is to process all the given operations.

Input

The first line of input contains two integers $$$N$$$ and $$$K$$$ $$$(1 \leq N, K \leq 10^{5})$$$, the size of $$$B$$$ and the number of operations respectively.

In the second line $$$N$$$ integer numbers $$$B_i$$$ $$$(1 \leq B_i \leq 10000)$$$ separated by a space.

Each of the next $$$K$$$ lines contains a single operation in the form: $$$C$$$ $$$l$$$ $$$r$$$, where $$$C$$$ is a character denoting the type of operation (Q, A, or R), and $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq N)$$$ define the range on which the operation is to be performed.

Output

For every operation of type Q, print a line with the result of the query.

Example
Input
10 10
1 2 3 4 5 6 7 8 9 10
Q 1 10
R 1 10
A 1 10
Q 1 10
R 1 7
Q 5 10
R 7 10
Q 6 10
A 6 10
Q 1 6
Output
10
10
10
9
8