Bob has n heap(s) of gravel (initially there are exactly c piece(s) in each). He wants to do m operation(s) with that heaps, each maybe:
- adding pieces of gravel onto the heaps from u to v, exactly k pieces for each,
- or querying "how many pieces of gravel are there in the heap p now?".
-----Request-----
Help Bob do operations of the second type.
-----Input-----
- The first line contains the integers n,m,c, respectively.
- m following lines, each forms:
- S u v k to describe an operation of the first type.
- Q p to describe an operation of the second type.
(Each integer on a same line, or between the characters S, Q and the integers is separated by at least one space character)
-----Output-----
For each operation of the second type, output (on a single line) an integer answering to the respective query (follows the respective Input order).
-----Example-----Input:
7 5 0
Q 7
S 1 7 1
Q 3
S 1 3 1
Q 3
Output:
0
1
2
-----Limitations-----
- 0<n≤106
- 0<m≤250 000
- 0<u≤v≤n
- 0≤c,k≤109
- 0<p≤n
def update(fenwick,n,ind,val):
 while(ind<=n):
  fenwick[ind]+=val;
  ind+=ind&(-ind)
def get(arr,ind):
 su=0
 while(ind>0):
  su+=arr[ind]
  ind-=ind&(-ind)
 return su
n,m,c=list(map(int,input().strip().split(" ")))
fenwick=[0]*(n+1)
for z in range(m):
 s=list(map(str,input().strip().split(" ")))
 if(s[0]=='S'):
  update(fenwick,n,(int)(s[1]),(int)(s[3]))
  update(fenwick,n,(int)(s[2])+1,-(int)(s[3]))
 else:
  print(get(fenwick,(int)(s[1]))+c)

def update(fenwick,n,ind,val):
 while(ind<=n):
  fenwick[ind]+=val;
  ind+=ind&(-ind)
def get(arr,ind):
 su=0
 while(ind>0):
  su+=arr[ind]
  ind-=ind&(-ind)
 return su
n,m,c=list(map(int,input().strip().split(" ")))
fenwick=[0]*(n+1)
for z in range(m):
 s=list(map(str,input().strip().split(" ")))
 if(s[0]=='S'):
  update(fenwick,n,(int)(s[1]),(int)(s[3]))
  update(fenwick,n,(int)(s[2])+1,-(int)(s[3]))
 else:
  print(get(fenwick,(int)(s[1]))+c)
