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

using namespace std;

#define int long long
#define dotimes(i, n) for (int i = 0, i##max__ = (n); i < i##max__; i++)
#define whole(f, x, ...) ([&](decltype((x)) c) { return (f)(begin(c), end(c), ## __VA_ARGS__); })(x)

int rint() {
  int x;
  scanf("%lld", &x);
  return x;
}

void wint(int x) {
  printf("%lld\n", x);
}

template<typename T> int size(T const& c) { return static_cast<int>(c.size()); }
template <typename T> bool maxs(T& a, T const& b) { return a < b ? a = b, true : false; }
template <typename T> bool mins(T& a, T const& b) { return a > b ? a = b, true : false; }

class fenwick_tree {
  vector<int> a;
public:
  fenwick_tree(int n) : a(n+1) {}
  void add(int i, int x) {
    int n = ::size(a) - 1;
    for (; i <= n; i += i & -i)
      a[i] += x;
  }
  int psum(int i) const {
    int r = 0;
    for (; i > 0; i -= i & -i)
      r += a[i];
    return r;
  }
};

signed main() {
  const int n = rint();
  const int q = rint();
  // b_i = a_i - a_{i-1} (conventionally a_0 = 0)
  // a_n = sum(i = 1, ..., n) b_i
  // b_s = a_s - a_{s-1} += x
  // b_{t+1} = a_{t+1} - a_t += -x
  fenwick_tree ft(n);
  dotimes(i, q) {
    if (rint())
      wint(ft.psum(rint()));
    else {
      const int s = rint();
      const int t = rint();
      const int x = rint();
      ft.add(s, x);
      if (t < n)
        ft.add(t+1, -x);
    }
  }
  return 0;
}