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>
#define ll long long
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

template<typename T>
struct segment_tree{
    function<T(T,T)> f = [](T a, T b){return min(a,b);};
    T inf=0;
    vector<T> value;
    int N;
    segment_tree(int n){
        N=1;
        while(N<n)N*=2;
        value.assign(2*N-1,inf);
    }
    segment_tree(int n, function<T(T,T)> func, T t1){
        N=1;
            while(N<n)N*=2;
        value.assign(2*N-1,t1);
        f=func;
        inf=t1;
    }
    ll update(int i){
        ll ans=0;
        i+=N-1;
        ans+=value[i];
        while(i>0){
            i=(i-1)/2;
            ans+=value[i];
        }
        return ans;
    }
    void query(T a,T b,ll n){
        return query(a,b,0,0,N,n);
    }
    void query(T a,T b, int k, int l, int r, ll n){
        if(r<=a || b<=l)return;
        if(a<=l && r<=b){
            value[k]+=n;
        }else{
            query(a,b,2*k+1,l,(l+r)/2,n);
            query(a,b,2*k+2,(l+r)/2,r,n);
        }
    }
    void print(){
        for(int i=0;i<ceil(log2(N))+1;i++){
            for(int j=0;j<(1<<i);j++){
                cout<<value[j+(1<<i)-1]<<((j==(1<<i)-1)?"":",");
            }
            cout<<endl;
        }
    }
};

int main(){
    ll n,q;
    cin>>n>>q;
    segment_tree<ll> tree(n);
    rep(i,q){
        ll com;
        cin>>com;
        if(com==0){
            ll s,t,x;
            cin>>s>>t>>x;
            tree.query(s-1, t, x);
        }else{
            ll i;
            cin>>i;
            cout<<tree.update(i-1)<<endl;;
        }
    }
}