Courage (the cowardly dog) lives with his master Muriel and her husband Eustace in the city of Nowhere. Eustace is a farmer but not a very good one. One fine day Courage was taking a stroll in Eustace's cropless field when he found seeds of a magical tree. He sowed them in the field and the next morning n magical apple trees grew on the previously cropless field. The number of apples on the ith tree is apples[i] (0 ≤ i < n). The number of apples on a tree may change as sometimes courage eats some apples from a tree and sometimes apples grow instantly on the trees (because they are MAGICAL!!).

Eustace wants to start a business of apples. So he frequently enquires Courage about the total number of apples present on a range of trees. A range of trees is denoted by two integers, l and r (0 ≤ l ≤ r < n) and includes the trees from l to r (both inclusive).

Courage is very loyal to Muriel and wants to keep some apples for her. So whenever Eustace asks about the total number of apples on a range, he deliberately doesn't count the apples on a tree, s, such that l ≤ s ≤ r and MIN(apples[l], apples[l+1], apples[l+2] ... apples[r]) = apples[s].

In other words, while calculating the sum of apples on the trees in a range, Courage doesn't include the apples on the tree that has the minimum number of apples in that range.

Input

The first line contains n, the number of magical trees.

The second line contains n non-negative integers that denote the array apples.

The third line contains a non negative integer p, which is the number of events that take place.

Now follow p lines. Each line will be of the form 'EAT x y' or 'GROW x y' or 'COUNT x y'.

'EAT x y' means that Courage ate x apples from the yth tree. (0 ≤ y < n)

'GROW x y' means that x apples grew magically on the yth tree (0 ≤ y < n).

And 'COUNT l r' means that Eustace has told Courage to count the number of apples on the range of trees from l to r, both inclusive.

Remember that the trees are indexed from 0.

Output

For each 'COUNT x y' event, output a single number that Courage tells to Eustace.

Constraints

1 ≤ n ≤ 100000

1 ≤ p ≤ 100000

0 ≤ apples[i] ≤ 10⁹

0 ≤ l ≤ r

0 ≤ y < n

The number of apples on a tree never exceeds 10⁹.

Sample:

Input:
10
6 5 12 48 3 20 4 2 3 7
6
COUNT 2 4
COUNT 7 9
GROW 12 4
COUNT 2 4
EAT 6 9
COUNT 7 9

Output:
60
10
63
5

Explanation of the Sample:

For 'COUNT 2 4', the sum of apples on trees 2,3 and 4 is 12+48+3=63. But as Courage doesn't include the apples on the tree with the minimum number of apples in the specified range (which in this case is the 4th tree), the number that he has to tell Eustace is 12+48=60.

For 'COUNT 7 9', the sum of apples on trees 7,8 and 9 is 2+3+7=12. In this case the tree with the minimum number of apples in the range is the 7th tree. So Courage tell Eustace the number 3+7=10

'GROW 12 4' means that the 4th tree, which has 3 apples, grows 12 more apples on it. So the number of apples on the 4th tree becomes 15.

For 'COUNT 2 4', the answer will be 48+15=63

'EAT 6 9' means that Courage eats 6 apples from the 9th tree. So the 9th tree now has 7-6=1 apple.

For 'COUNT 7 9, the answer will be 2+3=5.