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;

template <typename T>
struct SegmentTree {
  int SEG_LEN = 1;
  std::vector<T> node;
  SegmentTree(int n) {
    while (SEG_LEN < n) { SEG_LEN <<= 1; }
    node.assign(SEG_LEN*2, 0);
  }
  void add(int l, int r, T x) {
    l += SEG_LEN; r += SEG_LEN;
    while (l < r) {
      if (l & 1) { node[l++] += x; }
      if (r & 1) { node[r-1] += x; r--; }
      l >>= 1; r >>= 1;
    }
  }
  T get(int idx) {
    idx += SEG_LEN;
    T ret = node[idx];
    while (true) {
      idx >>= 1;
      if (idx == 0) { break; }
      ret += node[idx];
    }
    return ret;
  }
};
int main() {
  int n, q; cin >> n >> q;
  SegmentTree<long long> seg_tree(n);
  while (q--) {
    int com; cin >> com;
    if (com == 0) {
      int s, t, x; cin >> s >> t >> x;
      seg_tree.add(s, t+1, x);
    }
    if (com == 1) {
      int i; cin >> i;
      cout << seg_tree.get(i) << endl;
    }
  }
  return 0;
}