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>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const int vx[]={1,0,-1,0}, vy[]={0,1,0,-1};
const int sqrtN = 512;
const ll LINF=1e18;
const ld PI=abs(acos(-1));

struct Node{
	int data;
	
	Node(int data) : data(data) {};
	
	Node operator*(const Node r) const{
		return data + r.data;
	}
} e(0);

struct SqrtDecomposition{
	vector<Node> data;
	vector<Node> bucket;
	int N, K;

	SqrtDecomposition(int n) : N(n){
		K = (N + sqrtN - 1) / sqrtN;
		data.assign(K * sqrtN, e);
		bucket.assign(K, e);
	}
	
	void add(int a, int b, int x){
		for(int k = 0; k < K; k++){
			int l = k * sqrtN, r = (k + 1) * sqrtN;
			
			if(b<=l||r<=a) continue;
			if(a<=l&&r<=b) bucket[k] = bucket[k] * x;
			else{
				for(int i = max(a, l); i < min(b, r); i++){
					data[i] = data[i] * x;
				}
			}
		}
	}
	
	int get(int x){
		int k = x / sqrtN;
		
		return (data[x] * bucket[k]).data;
	}
};

int main(){
	int n,q; cin >> n >> q;
	SqrtDecomposition data(n);
	REP(i,0,q){
		int f; cin >> f;
		
		if(f == 0){
			int a,b,c; cin >> a >> b >> c;
			data.add(a, b + 1, c);
		}else if(f == 1){
			int a; cin >> a;
			cout << data.get(a) << endl;
		}
	}
	
	return 0;
}