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

Solution:
import math


def hoge(s, e, value):
    s += l
    e += l
    d, l_running, r_running = rank, 1, 1

    while l_running or r_running:
        l_end_node, r_end_node = s >> d, e >> d
        l_end_leaf = l_end_node << d, (l_end_node + 1 << d) - 1
        r_end_leaf = r_end_node << d, (r_end_node + 1 << d) - 1

        if l_end_node == r_end_node:
            if l_end_leaf[0] == s and r_end_leaf[1] == e:
                # match
                lazy[l_end_node] += value
                break
        else:
            if l_running:
                if l_end_leaf[0] == s:
                    # match
                    lazy[l_end_node] += value
                    l_running = 0
                # ??????????????????????????????????????????????¶?????????????????????´???
                elif l_end_node >> 1 << 1 == l_end_node and l_end_node+1 < r_end_node:
                    # match
                    lazy[l_end_node+1] += value

            if r_running:
                if r_end_leaf[1] == e:
                    # match
                    lazy[r_end_node] += value
                    r_running = 0
                elif r_end_node >> 1 << 1 == r_end_node-1 and l_end_node+1 < r_end_node:
                    # match
                    lazy[r_end_node-1] += value

        if d > 0:
            # propagation
            if l_running:
                lazy_left, lazy[l_end_node] = lazy[l_end_node], 0
                lazy[l_end_node << 1] += lazy_left
                lazy[(l_end_node << 1)+1] += lazy_left
            if r_running:
                lazy_right, lazy[r_end_node] = lazy[r_end_node], 0
                lazy[r_end_node << 1] += lazy_right
                lazy[(r_end_node << 1)+1] += lazy_right

        d -= 1

def get_value(i):
    i += l
    v = 0
    for j in range(rank, -1, -1):
        v += lazy[i>>j]
    return v + tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [0]*(2*l)
lazy = [0]*(2*l)
rank = int(math.log2(len(tree)))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        hoge(query[1]-1, query[2]-1, query[3])
    else:
        ap(get_value(query[1]-1))

print("\n".join((str(n) for n in ans)))