CPU Usage Monitoring

Bob needs to monitor the CPU usage on his computer throughout the day. He records events that affect the CPU usage. An event can either increase (or decrease) the CPU usage by a given integer value or set the CPU usage to an absolute integer value. Note that due to some inexplicable actions, the CPU usage might become negative.

Bob also performs two types of queries:

• Query Type 1: Given a range of update events from L to R (1-indexed), report the maximum CPU usage among the final values after each update in that range.
• Query Type 2: Given the same range of update events, report the maximum CPU usage ever observed during these updates. For each update, if it is an addition operation, consider the maximum between the CPU usage before the update and the CPU usage after the update; for a set operation, only the new CPU usage is considered. In addition, include the CPU usage prior to the first update in the range.

The updates and queries are provided as a sequence of instructions. The instructions have the following formats:

• U op x: An update event. Here, op is either '+' (for additive change) or '=' (for assignment), and x is an integer.
• Q t L R: A query event. Here, t is either 1 or 2 indicating the query type, and L and R are the 1-indexed boundaries that refer only to update events (queries themselves do not count as update events).

Initially, the CPU usage is 0. Process the instructions in order. For each query, output the answer on a separate line.

All formulas are given in LaTeX format when necessary. For instance, if an update adds a value x then the new CPU usage is computed as \(\text{new} = \text{old} + x\), and its intermediate maximum is \(\max(\text{old},\,\text{new})\). For a set operation, the CPU usage becomes \(x\).

inputFormat

The first line contains an integer T, the total number of instructions.

Each of the following T lines contains one instruction in one of the following formats:

• U op x — An update event. Here, op is either '+' (meaning the CPU usage is changed by addition) or '=' (meaning the CPU usage is set to x), and x is an integer.
• Q t L R — A query event. Here, t is the query type (1 or 2), and L and R (with 1-indexing) define the range of update events to consider. Note that only update events are numbered sequentially; query events do not count as updates.

outputFormat

For each query instruction, output a single integer on a separate line representing the answer to that query.

sample

8
U + 10
U -5
Q 1 1 2
Q 2 1 2
U = 8
U + 2
Q 1 3 4
Q 2 3 4

10
10
10
10