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 <bits/stdc++.h>

using namespace std;
int n , z;

pair < int , int > st[4*100000];

int op(int iz , int der)
{
	return st[iz].first + st[der].first;
}
void push(int v , int l , int r)
{
	if(r-l == 1)
		return;
	int m = (r+l)/2;
	st[2*v].second += st[v].second;
	st[2*v].first += st[v].second*(m-l);
	st[2*v+1].second += st[v].second;
	st[2*v+1].first += st[v].second*(r-m);
	st[v].second = 0;
}

void u(int v , int l , int r, int i , int j, int x)
{
	push(v , l , r);
	if(j < l || i >= r)
	{
		return;
	}else if(i <= l && r-1 <= j)
	{
		st[v].second += x;
		st[v].first += (r-l)*x;
	}else
	{
		int m = (r+l)/2;
		u(2*v , l , m , i , j , x);
		u(2*v+1 , m , r , i , j , x );
		st[v].first = op(2*v , 2*v+1);
	}
}



int q(int v , int l , int r , int x)
{
	push(v , l , r);
	if(x < l || x >= r)
	{
		return 0;
	}else
	{
		if(r - l == 1)
		{
			return st[v].first;
		}else
		{
			int m = (r+l)/2;
			return max(q(2*v , l , m , x) , q(2*v+1 , m , r , x ));
		}
	}
}


int main()
{
	cin >> n >> z;
	int a , b , c , d;
	while(z--)
	{
		cin >> a ;
		if(a == 0)
		{
			cin >> b >> c >> d;
			u(1,1,n+1,min(b,c),max(b,c),d);
		}else
		{
			cin >> b;
			cout << q(1,1,n+1,b) << '\n';
		}
	}
	return 0; 
}