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;

class SegTree{
private:
  int n;
  // 1-index (tree[0] is dummy), leaves are tree[n]-tree[2n-1]
  vector<int> tree;
  const int defVal = 0;
public:
  SegTree(int _n){
    int t;
    t = 1;
    while (t<_n) t*=2;
    n = t;
    tree = vector<int>(2*n, defVal);
    //cerr << "finish init" << endl;
    //cerr << "tree size is " << 2*n << endl;
  }
  // stab function
  void add(int l, int r, int x){ return _add(l,r,x,1,0,n);}
  void _add(int l, int r, int x, int k, int kl, int kr){
    //cerr << "add: "<<l<<" "<<r<<" "<<x<<" "<<k<<" "<<kl<<" "<<kr<<endl;
    if (kr<=l || r<=kl) return;
    else if (l<=kl && kr<=r){
      tree[k] += x;
      return;
    } else {
      if (tree[k]!=defVal){
        tree[k*2]+=tree[k]; tree[k*2+1]+=tree[k];
        tree[k]=defVal;
      }
      _add(l,r, x, k*2, kl,(kl+kr)/2);
      _add(l,r, x, k*2+1, (kl+kr)/2,kr);
    }
  }
  int get(int i){
    return _get(i,1,0,n);
  }
  int _get(int i, int k, int kl, int kr){
    //cerr << "get: "<<i<<" "<<k<<" "<<kl<<" "<<kr<<endl;
    if (k>=n) return tree[k];
    if (i<(kl+kr)/2) return tree[k]+_get(i, k*2, kl,(kl+kr)/2);
    else return tree[k]+_get(i, k*2+1, (kl+kr)/2,kr);
  }
  // debug
  void print(){
    cerr << "debug: ";
    for (int i=1; i<2*n; i++){
      if (i==n) cout << "| ";
      if (tree[i]==defVal) cout << "DV ";
      else cout << tree[i] << " ";
    }
    cout << endl;
  }
};

int main(void){
  int n,q;
  SegTree *st;
  
  cin >> n >> q;
  st = new SegTree(n);
  for (int i=0; i<q; i++){
    int c,s,t,x,id;
    cin >> c;
    if (c==0){
      cin >> s >> t >> x;
      st->add(s-1,t,x);
    }
    else if (c==1){
      cin >> id;
      cout << st->get(id-1) << endl;
    }
    else cout << "illegal command" << endl;
    //st->print();
  }
  return 0;
}