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 chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

class SquareDivision{
    private:
        const int BUCKET_SIZE=256;
        ll N, B;
        vector<ll> data, bucket_add;

    public:
        void prepare(int n){
            B=(n+BUCKET_SIZE-1)/BUCKET_SIZE;
            N=B*BUCKET_SIZE;
            data.assign(N, 0);
            bucket_add.assign(B, 0);
        }

        void add(int s, int t, int x){
            for(int i=0; i<B; i++){
                int l=i*BUCKET_SIZE, r=(i+1)*BUCKET_SIZE;

                if(r<=s || t<=l) continue;

                if(s<=l && r<=t){
                    bucket_add[i]+=x;
                }
                else{
                    for(int j=max(s, l); j<min(t, r); j++){
                        data[j]+=x;
                    }
                }
            }
        }

        int get(int i){
            int k=i/BUCKET_SIZE;
            return data[i]+bucket_add[k];
        }
};

signed main(){
    int n, q; cin>>n>>q;
    SquareDivision ans;
    ans.prepare(n);

    while(q--){
        int c; cin>>c;
        if(c==0){
            int s, t, x; cin>>s>>t>>x;
            ans.add(s, t+1, x);
        }
        else{
            int x; cin>>x;
            cout << ans.get(x) << endl;
        }
    }
}