Description

Bob needs a program to monitor CPU usage. This is a tedious task. To make it simpler, Bob will gradually list what he will do today while using the computer.

Bob does many things. Besides running brute-force programs and watching videos, he also goes out to play, randomly clicks the mouse, and might even kick out the power cord. Some actions increase or decrease the CPU usage by a value during the time they are performed; some actions directly set the CPU usage to a specific value.

Of course, Bob will ask: under the influence of the previously listed events, what is the maximum CPU usage in a certain time interval. Sometimes Bob will also curiously ask: in a certain time interval, what is the highest CPU usage that has ever been reached.

To be precise, usage is represented by an integer instead of a percentage.

It is not guaranteed that Bob's event list is free of weird issues that could make the usage negative...

Description

Input Format

The first line contains a positive integer $T$, the total time Bob needs to monitor the CPU.

The second line contains $T$ numbers indicating, before your monitoring program starts, the CPU usage that has already been reached at each moment within this time span.

The third line contains an integer $E$, the total number of actions and queries Bob will perform.

Each of the next $E$ lines is either a query or an event:

• Q X Y: Query the maximum current CPU usage from $X$ to $Y$ (under the effects of all events listed so far).
• A X Y: Query the highest CPU usage that has ever been reached from $X$ to $Y$ (over the entire history up to now).
• P X Y Z: List an event that increases the CPU usage by $Z$ from $X$ to $Y$.
• C X Y Z: List an event that sets the CPU usage to $Z$ from $X$ to $Y$.

Time is measured in seconds, and usage has no unit.

$X$ and $Y$ are positive integers ($X\le Y$), and $Z$ is an integer.

The interval from $X$ to $Y$ is inclusive of second $X$ and second $Y$.

It is guaranteed that all necessary operations fit within 32-bit signed integers.

Output Format

For each query, output one integer on its own line as the answer.

10
-62 -83 -9 -70 79 -78 -31 40 -18 -5 
20
A 2 7
A 4 4
Q 4 4
P 2 2 -74
P 7 9 -71
P 7 10 -8
A 10 10
A 5 9
C 1 8 10
Q 6 6
Q 8 10
A 1 7
P 9 9 96
A 5 5
P 8 10 -53
P 6 6 5
A 10 10
A 4 4
Q 1 5
P 4 9 -69

79
-70
-70
-5
79
10
10
79
79
-5
10
10

Hint

The testdata is distributed as follows:

• In testdata 1 and 2, $T$ and $E$ are both at most $10^3$.
• In testdata 3 and 4, there are only Q queries.
• In testdata 5 and 6, there are only C events.
• In testdata 7 and 8, there are only P events.

For $100\%$ of the testdata, $1\le T,E\le 10^5$, $1\le X\le Y\le T$, $-2^{31}\leq Z\lt 2^{31}$.

Translated by ChatGPT 5