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 JAVA):

Solution:
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();
		
		RaddQ rq = new RaddQ(n);
		
		for (int i = 0; i < q; i++) {
			int command = sc.nextInt();
			if(command == 0){
				int s = sc.nextInt();
				int t = sc.nextInt();
				int x = sc.nextInt();
				rq.add(0,n,0,s-1,t,x);
			} else if (command == 1) {
				int t = sc.nextInt();
				System.out.println(rq.get(0,n,0,t-1));
			}
		}
	}
}


class RaddQ { 
	int n, heap[];
	
	RaddQ(int n){
		this.n = n;
		
		int len = 1;
		while(len < n){
			len*=2;
		}
		len = 2*len;
		heap = new int[len];
	}
	

	
	void add(int l, int r, int ih, int s, int t, int x){
		if(s>=t){
			return;
		}
		if(s==l && t==r){
			heap[ih] += x;
			return;
		}
		int med = (l+r)/2;
		add(l, med, ih*2+1, Math.max(s,l), Math.min(t,med), x);
		add(med, r, ih*2+2, Math.max(s,med), Math.min(t,r), x);
	}
	
	
	int get(int l, int r, int ih, int t){
		if(r-l == 1){
			return heap[ih];
		}
		int med = (l+r)/2;
		if(t<med){
			return heap[ih]+get(l, med, ih*2+1, t);
		} else {
			return heap[ih]+get(med, r, ih*2+2, t);
		}
	}
}