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 <iostream>
#include <vector>

using namespace std;

// Segment tree. Modification (Add) on interval, single element access.

template<typename T>
class SegTree{
    size_t n;
    vector<T> data;
public:
    SegTree(size_t _n): n(_n), data(2 * n, 0){}
    SegTree(const vector<T> &src): n(src.size()), data(2 * n, 0){init(src);}
    void init(const vector<T> &src){
        for (size_t i = 0; i != n; ++i) data[n + i] = src[i];
    }
    void add(size_t L, size_t R, T v){ // add v to interval [L, R)
        for (L += n, R += n; L < R; L >>= 1, R >>= 1){
            if (L & 1) data[L++] += v;
            if (R & 1) data[--R] += v;
        }
    }
    T query(size_t i){
        T ret = 0;
        for (i += n; i > 0; i >>= 1) ret += data[i];
        return ret;
    }
    void push(){
        for (size_t i = 1; i < n; ++i){
            data[i<<1] += data[i];
            data[i<<1|1] += data[i];
            data[i] = 0;
        }
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    SegTree<int> seg(n);
    while (q--){
        int c;
        cin >> c;
        if (c == 0){
            int s, t, x;
            cin >> s >> t >> x;
            seg.add(s - 1, t, x);
        }else{
            int i;
            cin >> i;
            cout << seg.query(i - 1) << '\n';
        }
    }
    return 0;
}