F. Farmer Faul
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Faul decided to become a farmer, and he grows bamboo!

Faul has n bamboo stalks numbered from 1 to n, and he can do three operations on them. He can cut and harvest all of the bamboo at a certain height, order a single bamboo stalk to grow, or use magic to make all bamboo stalks grow.

Faul knows exactly what his next q operations will be. Each operation will be one of the three types.

  • CUT h. Faul cuts all the bamboo stalks at height h (1 ≤ h ≤ 106). More precisely, if a stalk is higher than height h, then the part higher than h will be cut off and harvested. For this query, you should output one integer, on a line by itself, representing the total length of bamboo harvested by this cut.
  • GROW i x. Faul orders the ith stalk to grow by x (1 ≤ i ≤ n;1 ≤ x ≤ 106). More precisely, if stalk i was at height k, then this query makes it grow to height k + x.
  • MAGIC y. Faul uses magic to make all bamboo stalks grow by y (1 ≤ y ≤ 106).

Since Faul has more important things to tend to (such as badminton), he wants you to help him predict the amount of bamboo he will harvest after each cut.

Input

The first line of input contains two space-separated integers n and q (1 ≤ n ≤ 106;1 ≤ q ≤ 106).

The second line of input contains n space-separated integers hi (1 ≤ hi ≤ 106), where hi is the initial height of the ith bamboo stalk.

Each of the next q lines contains a query. Each query is one of the three aforementioned types.

Output

For each CUT query, output a single integer, on a line by itself, that is the total length of bamboo harvested by that cut.

Example
Input
4 5
1 2 3 3
GROW 3 1
CUT 2
MAGIC 2
CUT 2
CUT 7
Output
3
7
0
Note

In the first sample, we do the following.

  • GROW 3 1. We grow the third bamboo by 1. Now the heights are 1 2 4 3.
  • CUT 2. We cut everything at height 2, so we cut 2 and 1 units from the third and fourth bamboos respectively. We output 3 since 1 + 2 = 3. Now the heights are 1 2 2 2.
  • MAGIC 2. We grow all the bamboos by 2. Now the heights are 3 4 4 4.
  • CUT 2. We cut everything at height 2. We cut 1 unit from bamboo 1, and we cut 2 units from bamboos 2, 3, and 4. We output 7 since 1 + 2 + 2 + 2 = 7. Now the heights are 2 2 2 2.
  • CUT 7. We cut everything at height 7. No bamboo is higher than 7 so nothing is cut. We output 0 and the heights remain unchanged.