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:
class TemplateTree:
  def __init__(self, iterable):
    self.iter_size = self.get_size(iterable)
    self.size = self.iter_size * 2 - 1
    self.value = [None] * self.size
    for i, v in enumerate(iterable):
      self.value[self.iter_size + i - 1] = v
    self.set_value(0)
    self.range = [None] * self.size
    self.set_range(0, 0, self.iter_size - 1)
  
  def get_size(self, iterable):
    ret = 1
    x = len(iterable)
    while ret < x:
      ret *= 2
    return ret
  
  def set_range(self, x, left, right):
    self.range[x] = (left, right)
    if left != right:
      self.set_range(x * 2 + 1, left, (right + left) // 2)
      self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

  def set_value(self, x):
    if x >= self.iter_size - 1:return self.value[x]
    a = self.set_value(x * 2 + 1)
    b = self.set_value(x * 2 + 2)
    if a == None and b == None:
      self.value[x] = None
    elif a == None:
      self.value[x] = b
    elif b == None:
      self.value[x] = a
    else:
      self.value[x] = a
    return self.value[x]

  def update(self, x, add, left, right):
    x_left, x_right = self.range[x]
    if right < x_left or x_right < left:
      pass
    elif left <= x_left and x_right <= right:
      self.value[x] += add
    else:
      self.update(x * 2 + 1, add, left, right)
      self.update(x * 2 + 2, add, left, right)
  
  def query(self, x, total):
    if x < 0:return total
    total += self.value[x]
    return self.query((x - 1) // 2, total)

  def print_tree(self):
    print(self.value)
    print(self.range)

n, q = map(int, input().split())
tree = TemplateTree([0] * n)

for _ in range(q):
  lst = list(map(int, input().split()))
  if lst[0] == 0:
    s, t, x = lst[1:]
    tree.update(0, x, s - 1, t - 1)
  else:
    i = lst[1]
    print(tree.query(tree.iter_size - 1 + i - 1, 0))