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;

template<class T> struct DualSegmentTree {
    using F = function<T(T, T)>;
private : 
    int n, dep;
    const F f;
    T id;
    vector<T> node;

public : 
    DualSegmentTree (const F &f, const T &id) : f(f), id(id) { }

    void init (int sz) {
        n = 1; dep = 0;
        while (n < sz) { n <<= 1; dep++; }
        node.resize(2 * n, id);
    }

    void build (const vector<T> v) {
        const int sz = (int)v.size();
        init(sz);
        for (int i = 0; i < sz; i++) node[i] = v[i];
    }

    inline void eval (int k) {
        if (node[k] == id) return;
        node[k<<1|0] = f(node[k<<1|0], node[k]);
        node[k<<1|1] = f(node[k<<1|1], node[k]);
        node[k] = id;
    }

    inline void thrust (int k) {
        for (int i = dep; i; i--) eval(k>>i);
    }

    void update (int a, int b, T x) {
        thrust(a += n);
        thrust(b += n - 1);
        for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
            if (l&1) { node[l] = f(node[l], x); l++; }
            if (r&1) { r--; node[r] = f(node[r], x); }
        }
    }

    const T &operator[] (int i) {
        thrust(i += n);
        return node[i];
    }

};

int main() {
    int n, q, op, s, t, x, i;
    cin >> n >> q;
    
    auto f = [] (int a, int b) { return a + b; };
    DualSegmentTree<int> seg(f, 0);
    seg.init(n);
    
    while (q--) {
        cin >> op;
        if (op) {
            cin >> i;
            cout << seg[--i] << endl;
        } else {
            cin >> s >> t >> x;
            seg.update(s-1, t, x);
        }
    }
    return 0;
}