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.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

class LazySegmentTree {
	int[] nodes;
	int[] lazy;

	int n;
	int e = 0; // 単位元

	public LazySegmentTree(int size) {
		n = 1;
		while (n < size) {
			n *= 2;
		}

		nodes = new int[2 * n - 1];
		lazy = new int[2 * n - 1];

		Arrays.fill(nodes, e);
		Arrays.fill(lazy, e);
	}

	public void eval(int k) {
		if (lazy[k] == e) {
			return;
		}

		// 葉でないなら
		if (k < n - 1) {
			lazy[2 * k + 1] += lazy[k];
			lazy[2 * k + 2] += lazy[k];
		}

		nodes[k] += lazy[k];
		lazy[k] = 0;
	}

	public void add(int a, int b, int val) {
		add(a, b, val, 0, 0, n);
	}

	private void add(int a, int b, int val, int k, int l, int r) {
		// [l,r) が[a,b) に含まれていない場合
		if (a >= r || b <= l) {
			return;
		}

		eval(k);

		if (a <= l && r <= b) {
			lazy[k] += val;
			eval(k);
			return;
		}

		add(a, b, val, 2 * k + 1, l, (l + r) / 2);
		add(a, b, val, 2 * k + 2, (l + r) / 2, r);

		nodes[k] = Math.max(nodes[2 * k + 1], nodes[2 * k + 2]);
	}

	public int query(int a, int b) {
		return query(a, b, 0, 0, n);
	}

	private int query(int a, int b, int k, int l, int r) {
		if (a >= r || b <= l) {
			return e;
		}
		eval(k);
		if (a <= l && r <= b) {
			return nodes[k];
		}

		int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
		int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);

		return Math.max(vl, vr);

	}
	
}

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int n = sc.nextInt();
		int q = sc.nextInt();

		LazySegmentTree seg = new LazySegmentTree(n);

		for (int i = 0; i < q; i++) {
			int c = sc.nextInt();

			if (c == 0) {
				int s = sc.nextInt() - 1;
				int t = sc.nextInt();
				int x = sc.nextInt();

				seg.add(s, t, x);

			} else {
				int a = sc.nextInt() - 1;
				out.println(seg.query(a, a + 1));
			}
		}

		sc.close();

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}