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;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
#define fi first
#define se second
#define sc scanf
#define pr printf
#define pb push_back
const ll inf = 1e18;
const int nax = 2e6 + 7;
ll mod;
int n , q;
using namespace std;
ll exp(ll a , ll b){
	if(b == 0)	return 1;
	int x = b % 2 == 0 ?   ((exp(a , b/2)%mod)*(exp(a , b / 2)%mod))%mod :  (a%mod*exp(a , b - 1) % mod)%mod;
	return x;
}
ll tree[nax];
ll arr[nax];
void update(int l , int r , int val , int tl , int tr , int pos){
	if(l > r)
		return ;
	if(tl == l && tr == r){
		tree[pos] += val;
		return ;
	}
	int mid = tl + (tr - tl)/2;
	update(l , min(r , mid),val ,  tl , mid , 2 * pos );
	update(max(l , mid + 1), r , val , mid + 1 , tr , 2 * pos + 1);
	//tree[pos] = tree[2*pos] + tree[ 2* pos + 1];
}
ll query(int ind, int tl , int tr , int pos){
	if(tl == tr)
		return tree[pos];
	int mid = tl + (tr - tl)/2;
	if(ind <= mid)
		return tree[pos] + query(ind , tl , mid , 2*pos);
	else 
		return tree[pos] + query(ind , mid + 1 , tr , 2*pos + 1);	
}
int main(int argc,char ** argv){
	dhoom;

	cin >> n >> q;
	for(int i = 0 ; i < q ; i++){
		int a , b , c , d;
		cin >> a;
		if(a == 0){
				cin >> b >> c >> d;
				update(b , c , d , 1 , n , 1);
		}
		else
		{
				cin >> b;
				cout << query(b , 1 , n , 1) << endl;
		}
	}
	return 0;
		
}