Background

Problem Setter: All OIers must be careful!!! Read the notes carefully.

Problem Setter: Chen_Xi.Naoh

Zero and Mike are two good friends who love traveling. One day, after going through the training of the great ZXG, they were exhausted, so they decided to go back to the hotel on the Double Ninth Festival to do problems and regain their confidence. Thus, our story begins.

Problem Description

Zero’s hotel room number is $703$, and Mike’s hotel room number is $704$. So when Zero and Mike want to get together to do problems, Zero needs to go from $703$ to $704$, or Mike goes from $704$ to $703$. When they are together, Mike will randomly choose $n$ problems from luogu . Each problem is worth $300$ points. Since Mike is very experienced, whenever he sees a problem, his brain will automatically assign it a difficulty value $hard$ (trust that Mike’s judgment is always correct). Both Zero and Mike share a common talent value $Talent$. Each person can only AC problems whose difficulty is within $Talent$ (that is, problems satisfying $hard \le Talent$). Of course, Zero and Mike’s talent value will not be very low.

In Zero’s room $703$, there is a junior student BookCity who loves studying. While Zero and Mike are doing problems, BookCity will study their habits and cheer for them. Because of BookCity’s cheering, the difficulty of a certain problem will automatically decrease by $d$ (if $hard - d \le 0$, then the $hard$ of this problem is set to $1$ by default). However, in room $123$ of the hotel lives a magical but evil person Guy, who can observe Zero and Mike and cast magic (because it is the Double Ninth Festival). When Zero and Mike are solving a certain problem, he can directly increase that problem’s difficulty $hard$ to $s$ times its original value!!!!! Fortunately, Zero and Mike’s teacher tingtime will help them: in difficult situations, he will guide them and directly set the difficulty of a certain problem to a very low value $x$.

For each problem they finish, Zero and Mike gain confidence corresponding to its score (they both pursue perfection: each problem is either solved correctly, or not written at all). Now you are Zero. You want to know how much confidence $Confidence$ can be recovered if you and Mike solve problems from problem $a$ to problem $b$ (confidence calculation: $Confidence = 600 \times$ number of AC problems $\Longrightarrow$ one problem is $300$ points, and with $2$ people, they recover $600$ confidence in total).

Input Format

The first line contains two integers, representing the number of problems $n$ and the talent value $Talent$.

The second line contains $n$ integers. The $i$-th integer denotes the $hard$ value of problem $i$.

The third line contains one integer, representing the number of events $m$.

In the next $m$ lines, each line contains a string $S$ and $2$ integers, describing a valid event:

• If $S=\texttt{BookCity}$, it is a BookCity event. The next two numbers $i,d$ mean setting the difficulty $hard_i$ of problem $i$ to $\max(hard_i-d,1)$.
• If $S=\texttt{Guy}$, it is a Guy event. The next two numbers $i,d$ mean setting the difficulty $hard_i$ of problem $i$ to $hard_i \times d$.
• If $S=\texttt{tingtime}$, it is a tingtime event. The next two numbers $i,d$ mean setting the difficulty $hard_i$ of problem $i$ to $d$.
• If $S=\texttt{Zero}$, it is a Zero event. The next two numbers $a,b$ represent a query: the amount of confidence $Confidence$ recovered by solving problems from problem $a$ to problem $b$.

It is strictly guaranteed that all events happen in order.

Output Format

For each Zero event, output one line with one number: the answer $Confidence$ for that event.

5 5
2 3 4 5 9
5 
BookCity 1 1
Guy 2 5
Zero 1 5
tingtime 5 1
Zero 1 5

1800
2400

Hint

Constraints:

• All initial difficulty values $hard$ are in the range $[0,2^{31}-1]$.
• Zero and Mike’s talent value $Talent$ is in the range $[0,2^{31}-1]$.
• In Zero events, $a,b$ are in the range $[0,2^{31}-1]$, but it is not guaranteed that $a<b$.
• In Guy events, $d$ is in the range $[0,2^{31}-1]$.
• In BookCity events, $d$ is in the range $[0,2^{31}-1]$.
• All input data are in the range $[0,2^{31}-1]$.
• Since Mike is very experienced, the $hard$ values he assigns are in the range $[0,2^{31}-1]$, and there are no problems with negative difficulty or difficulty $0$ (free points).
• Both $n$ and $m$ are in the range $[0,2^{31}-1]$.

For $30\%$ of the testdata: $0 \leqslant n \leqslant 5\times 10^3$, $m \leqslant 5\times 10^3$.

For $50\%$ of the testdata: $0 \leqslant n \leqslant 5\times 10^4$, $m \leqslant 5\times 10^4$.

For $100\%$ of the testdata: $0 \leqslant n \leqslant 5\times 10^5$, $m \leqslant 5\times 10^5$.

In short, all input data are guaranteed to be in the range $[0,2^{31}-1]$, but intermediate computations are not guaranteed to stay within the range $[0,2^{63}-1]$!!

Translated by ChatGPT 5