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 rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define pvec(vec) {for (auto v: vec) cout << v << ' '; cout << endl;}
#define pivec(vec) {rep(i, 0, vec.size()) cout << i << ':' << vec[i] << ' '; cout << endl;}

using namespace std;
using ll = long long;

int main()
{
    int n, q;
    cin >> n >> q;

    int root_n;
    for(root_n=1; root_n*root_n<n; ++root_n);

    // initialize container
    vector<int> array(n, 0);
    vector<int> blocks(root_n, 0);

    rep(_, 0, q)
    {
        int com;
        cin >> com;

        if (com == 0)
        {
            int s, t, x;
            cin >> s >> t >> x;
            --s, --t;

            // ex)
            //  s       t 
            // AAA BBB CCC
            //  0   1   2
            // block_s -> 1
            // block_t -> 1
            int block_s = s/root_n + 1;
            int block_t = t/root_n - 1;
            // cout << block_s << ' ' << block_t << endl;
            
            rep(i, block_s, block_t+1)
                blocks[i] += x;
            for(int i=s; i<block_s*root_n and i <=t; ++i)
                array[i] += x;

            // if s and t are at same block
            if (block_s-1==block_t+1) continue;

            for (int i=(block_t+1)*root_n; i<=t; ++i)
                array[i] +=x;

            // cout << "*-----------" << endl;
            // pvec(blocks);
            // pvec(array);
        }
        else
        {
            int t;
            cin >> t;
            --t;
            printf("%d\n", array[t] + blocks[t/root_n]);
        }
    }
    return 0;
}