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<iostream>
#include<algorithm>
#include <stdio.h>
using namespace std;
#define TREE_N (1<<17)

int ans,c,n,tree[ TREE_N * 2 -1]={};

void update(int i){
  i+=TREE_N-1;
  ans+=tree[i];
  while(i>0){
    i=(i-1)/2;
    ans+=tree[i];
  }
}

void rec(int a,int b,int k=0,int l=0,int r=TREE_N){
  if((l<a&&a<r)||(l<b&&b<r)){
    int m=(l+r)/2;
    rec(a,b,k*2+1,l,m);
    rec(a,b,k*2+2,m,r);
  }else if(a<=l&&r<=b){
    tree[k]+=c;
  }
}

int Rec(int a,int b,int k=0,int l=0,int r=TREE_N){
  if((l<a&&a<r)||(l<b&&b<r)){
    int m=(l+r)/2;
    int left = Rec(a,b,k*2+1,l,m);
    int right = Rec(a,b,k*2+2,m,r);
    return min(left,right);
    
  }else if(a<=l&&r<=b){
    return tree[k];
  }else{
    return 2147483647;
  }
}

int main(){
  int q,com,a,b;
  cin>>n>>q;
  for(int i=0;i<q;i++){
    cin>>com;
    if(com){
      cin>>a;
      ans=0;
      update(a);
      printf("%d\n",ans);
    }
    else {
      cin>>a>>b>>c;
      rec(a,b+1);
    }
  }
  return 0;
}