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

Solution:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>

using namespace std;

typedef long long int64;
typedef unsigned long long uint64;
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> ipair;
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)

const int maxn=1<<20;

int n,m,c;
double s[maxn];

double sum(int i)
{
double r=0;
for (;i;i&=(i-1)) r+=s[i];
return r;
}
void update(int i,double d)
{
for (;i<=n;i=(i|(i-1))+1) s[i]+=d;
}
int main()
{
scanf(“%d%d%d”,&n,&m,&c);
memset(s,0,sizeof(int64)*(n+1));
update(1,c);
for (;m>0;m–)
{
char str[10];
scanf(“%s”,str);
if (str[0]==’Q’)
{
int p;
scanf(“%d”,&p);
printf(“%.0lfn”,sum(p));
}
else
{
int u,v,d;
scanf(“%d%d%d”,&u,&v,&d);
update(u,d);
update(v+1,-d);
}
}
return 0;
}