Generals have n soldiers under the hands of the South, which are numbered 1 to N, respectively. The number of enemies of these soldiers is known.

Small worker is a military division under the southern general. Generals of the South often want to know the total number of killings from the Militan to No. N soldiers. Please help the small worker to answer the Southern General.

After a certain inquiry of General

, the soldier I might kill the enemy Q again. After the Southern General asked again, it was necessary to consider the number of new enemies.

input

There is only one set of test data
The first line is two integer n, m, where n means the number of soldiers (1 <n <1000000), M means the number of instructions. (1 <m <100000)
The subsequent line was N intersection, and AI said that the number of soldiers No. i killed the enemy. (0 <= AI <= 100)
Subsequent M lines each line is a instruction. This instruction contains a string and two integers. The first is a string. If it is a string Query M, n, indicating the starting and termination soldier number of the query; if it is a string ADD, the two integers followed by the back I, A (1 <= i <= n, 1 <= a <= 100), which means i i i The number of soldiers killed the enemy was A.

output

For each query, output an integer R represents the total number of killing enemies of the soldiers to No. N soldiers, each group output accounts for one line

Sample input

5 6
1 2 3 4 5
QUERY 1 3
ADD 1 2
QUERY 1 3
ADD 2 3
QUERY 1 2
QUERY 1 5

Sample output

6
8
8
20

Single -point update.

#include <iOSTREAM> 
 #include <algorithm> 
 #include <cstdio> 
 #include <cstring> 
 #Define Maxn 1000010 
 using namespace std; 
 int Array [maxn]; 
 int segt [maxn * 4 + 10]; 
 void Build (int Node, int BEGIN, int End) {{ 
 if (begin == end) { 
 segt [node] = array [begin]; 
 } 
 else { 
 Build (node * 2, begin, (begin + end) / 2); 
 Build (node * 2 + 1, (begin + end) / 2 + 1, end); 
 segt [node] = segt [node * 2] + segt [node * 2 + 1]; 
 } 
 } 
 int Query (int Node, int Begin, int End, int L, int R) { 
 if (begin == l && end == r) { 
 Return segt [node]; 
 } 
 else { 
 int Mid = (Begin + End) / 2; 
 if (R <= MID) Return Query (Node * 2, Begin, MID, L, R); 
 else if (L> MID) Return Query (Node * 2 + 1, MID + 1, END, L, R); 
 Else Return Query (Node * 2, Begin, MID, L, MID) + Query (Node * 2 + 1, MID + 1, END, MID + 1, R); 
 } 
 } 
 Void Updata (int Node, int Begin, int End, int ID, int ADD) {// single -point update 
 if (begin == end) {// In the end, you must find a point based on this condition, and this point is ID 
 segt [node] += ADD; 
 } 
 else { 
 int Mid = (Begin + End) / 2; 
 if (id <= mid) updata (node * 2, begin, mid, ID, add); // Find some positions on the online tree tree according to ID 
 Else Updata (Node * 2 + 1, MID + 1, END, ID, Add); 
 segt [node] = segt [node * 2] + segt [node * 2 + 1]; // Update the parent node 
 } 
 } 
 int Main () { 
     int n, m; 
     scanf (" %d %d", & n, & m); 
     int i; 
     for (i = 1; i <= n; i ++) { 
     scanf ("%d", & array [i]); 
 } 
 Build (1, 1, n); 
 char ch [10]; 
 int L, R; 
 While (m--) { 
 scanf ("%s", ch); 
 scanf (" %d %d", & l, & r); 
 if (strcmp (ch, "query") == 0) propf ("%d \ n", query (1, 1, n, l, r)); 
 else updata (1, 1, n, l, r); 
 } 
     Return 0; 
 }