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

using namespace std;

#define int long long

//int sqrtN;
int N,K;
const int sqrtN=512;
vector<int> data;
vector<int> bucketadd;

void init(){
	K=(N+sqrtN-1)/sqrtN;
	data.assign(K*sqrtN,0);
	bucketadd.assign(K,0);
}

void add(int s,int t,int x){
	for(int k=0;k<K;k++){
		int l=k*sqrtN;
		int r=(k+1)*sqrtN;
		if(r<=s || t<=l) continue;
		if(s<=l && r<=t) bucketadd[k]+=x;
		else{
			for(int i=max(s,l);i<min(t,r);i++){
				data[i]+=x;
			}
		}
	}
}

void get_i(int i){
	int k=i/sqrtN;
	//printf("%lld\n",data[i]+bucketadd[k]);
	printf("%lld\n",data[i]+bucketadd[k]);
}

signed main(){
	int q,com;
	int s,t,x;
	scanf("%lld %lld",&N,&q);
	//sqrtN = (int)sqrt(N);
	//printf("sqrt(N)=%lld\n",sqrtN);
	init();
	for(int i=0;i<q;i++){
		scanf("%lld",&com);
		if(com==0){
			scanf("%lld %lld %lld",&s,&t,&x);
			add(s,t+1,x);//[s,t)
		}
		else{
			scanf("%lld",&x);
			get_i(x);
		}
	}
}