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>

typedef std::pair<int,int> TV; // Time and Value

void add(TV* A, int s, int t, int index, int l, int r, int time, int val)
{
	if (t<l || r<=s) return; // no intersection
	else if (s<=l && r<=t+1) { // [l,r) is contained in [s,t] 
		A[index].first = time;
		A[index].second += val;
		return;
	}
	else { // at least one end exceeds the range
		int mid = (l+r)/2;
		add(A, s, t, 2*index+1, l, mid, time, val);
		add(A, s, t, 2*index+2, mid, r, time, val);
	}
}

int get(TV* A, int k, int index, int l, int r)
{
	if (l+1==r) return A[index].second;
	
	int mid = (l+r)/2;

	if (k<mid) return A[index].second + get(A, k, 2*index+1, l, mid);
	else return A[index].second + get(A, k, 2*index+2, mid, r);
}

int main ()
{
	int n, q;
	std::cin >> n >> q;
	
	int a_size = 1;
	for(; a_size<n; a_size<<=1);
	TV* A = new TV[2*a_size-1];
	for (int i=0; i<2*a_size-1; i++) {
		A[i].first = -1;
		A[i].second = 0;
	}
	
	
	for (int i=0; i<q; i++) {
		int op, s, t, x, k;
		std::cin >> op;
		if (op==0) {
			std::cin >> s >> t >> x;
			add(A, s-1, t-1, 0, 0, n, i, x);
		} else {
			std::cin >> k;
			std::cout << get(A, k-1, 0, 0, n) << std::endl;
		}
	}
	
	delete[] A;
	
	return 0;
}