Problem: Write a program which manipulates a sequence A = {a1, a2, . . . , an} with the following operations:

* add(s, t, x): add x to as, as+1, ..., at.
* get(i): output the value of ai.



Note that the initial values of ai (i = 1, 2, . . . , n) are 0.

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 100000
* 1 ≤ s ≤ t ≤ n
* 1 ≤ i ≤ n
* 0 ≤ x ≤ 1000

Input


n q
query1
query2
:
queryq


In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:


0 s t x


or


1 t


The first digit represents the type of the query. '0' denotes add(s, t, x) and '1' denotes get(i).

Output

For each get operation, print the value.

Examples

Input

3 5
0 1 2 1
0 2 3 2
0 3 3 3
1 2
1 3


Output

3
5


Input

4 3
1 2
0 1 4 1
1 2


Output

0
1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

struct BIT{
  ll bit[101010+1];

  void init(){
    memset(bit,0,sizeof(bit));
  }

  ll sum(int i){
    i++;
    ll s=0;
    while(i>0){
      s+=bit[i];
      i-=i&-i;
    }
    return s;
  }

  void add(int i,ll v){
    i++;
    while(i<=101010){
      bit[i]+=v;
      i+=i&-i;
    }
  }
};

struct RangeSumQuery{
  BIT bit0, bit1;

  RangeSumQuery(){}

  void init() {
    bit0.init();
    bit1.init();
  }

  ll sum(int from, int to) {
    return (bit0.sum(to)+bit1.sum(to)*to) - (bit0.sum(from)+bit1.sum(from)*from);
  }

  void add(int from, int to, ll value) {
    bit0.add(to, to * value);
    bit0.add(from, - from * value);
    bit1.add(from, value);
    bit1.add(to, -value);
  }
};


int main(){
	cin.sync_with_stdio(false);
  RangeSumQuery rsq;
  rsq.init();
  ll n,q;
  cin>>n>>q;
  while(q--){
    ll ty;
    cin>>ty;
    if(ty){
      ll i;
      cin>>i;
      i--;
      cout<<rsq.sum(i,i+1)<<endl;
    }else{
      ll s,t,x;
      cin>>s>>t>>x;
      s--;
      rsq.add(s,t,x);
    }
  }
	return 0;
}