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

class Bit {
	std::vector<int> _array;
	void add(int to, int add_value) {
		while (to >= 0) {
			_array[to] += add_value;
			to -= ~to & (to + 1);
		}
	}
public:
	Bit(int size) :_array(size, 0) {}
	void add(int from, int to, int add_value) {
		--from; --to;
		add(to, add_value);
		add(from - 1, -add_value);
	}
	int get(int pos) const {
		--pos;
		int res = 0;
		while (pos < _array.size()) {
			res += _array[pos];
			pos += ~pos & (pos + 1);
		}
		return res;
	}
};
int main() {
	int n, q;
	std::cin >> n >> q;
	int query, s, t, x, i;
	Bit bit(n);
	for (auto count = 0; count < q; ++count) {
		std::cin >> query;
		switch (query) {
		case 0:
			std::cin >> s >> t >> x;
			bit.add(s, t, x); break;
		case 1:
			std::cin >> i;
			std::cout << bit.get(i) << std::endl;
		}
	}
}
