There is a system of n vessels arranged one above the other as shown in the figure below. Assume that the vessels are numbered from 1 to n, in the order from the highest to the lowest, the volume of the i-th vessel is a_{i} liters. [Image] 

Initially, all the vessels are empty. In some vessels water is poured. All the water that overflows from the i-th vessel goes to the (i + 1)-th one. The liquid that overflows from the n-th vessel spills on the floor.

Your task is to simulate pouring water into the vessels. To do this, you will need to handle two types of queries:  Add x_{i} liters of water to the p_{i}-th vessel;  Print the number of liters of water in the k_{i}-th vessel. 

When you reply to the second request you can assume that all the water poured up to this point, has already overflown between the vessels.


-----Input-----

The first line contains integer n — the number of vessels (1 ≤ n ≤ 2·10^5). The second line contains n integers a_1, a_2, ..., a_{n} — the vessels' capacities (1 ≤ a_{i} ≤ 10^9). The vessels' capacities do not necessarily increase from the top vessels to the bottom ones (see the second sample). The third line contains integer m — the number of queries (1 ≤ m ≤ 2·10^5). Each of the next m lines contains the description of one query. The query of the first type is represented as "1 p_{i} x_{i}", the query of the second type is represented as "2 k_{i}" (1 ≤ p_{i} ≤ n, 1 ≤ x_{i} ≤ 10^9, 1 ≤ k_{i} ≤ n).


-----Output-----

For each query, print on a single line the number of liters of water in the corresponding vessel.


-----Examples-----
Input
2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2

Output
4
5
8

Input
3
5 10 8
6
1 1 12
2 2
1 1 6
1 3 2
2 2
2 3

Output
7
10
5

Difficulty: interview

Starter code:

Solutions:
n = int(input()) + 1
a = list(map(int, input().split())) + [1 << 50]
l, p, r = [0] * n, list(range(n)), []

for i in range(int(input())):
    t = list(map(int, input().split()))
    if t[0] == 2:
        r.append(l[t[1] - 1])
    else:
        x = t[1] - 1
        s, d = [x], t[2]
        while True:
            if p[x] != x:
                x = p[x]
                s.append(x)
                continue
            if l[x] + d < a[x]:
                l[x] += d
                break
            d -= a[x] - l[x]
            l[x] = a[x]
            x += 1
            s.append(x)
        for j in s:
            p[j] = x
        
print('\n'.join(map(str, r)))

__author__ = 'Utena'
import copy
n=int(input())
ocu=[0]+list(map(int,input().split()))
V=dict()
for i in range(1,n+1):
    V[i]=ocu[i]
ocu=[0]*(n+1)
stream=[0]*(n+1)
l=0
ans=[]
for i in range(1,n):
    stream[i]=i+1
stream[n]=0
m=int(input())
for i in range(m):
    s=list(map(int,input().split()))
    if s[0]==1:
        x0,p=s[1],s[2]
        x=x0
        temp1=set()
        while True:
            if p<V[x]-ocu[x]:
                ocu[x]+=p
                break
            else:
                p-=V[x]-ocu[x]
                ocu[x]=V[x]
                temp1.add(x)
                x=stream[x]
                if x==0:break
        for a in temp1:
            stream[a]=x
    if s[0]==2:
        ans.append(ocu[s[1]])
print('\n'.join(map(str,ans)))

n=int(input())
a=list(map(int,input().split()))
vessels=[]
ans=[]
index=[]
for i in range(n):
    vessels.append([0,a[i]])
    index.append(i+1)    
m=int(input())
for i in range(m):
    a=input()
    if a[0]=='1':
        a,p,x=list(map(int,a.split()))
        p-=1
        tt=set()
        while p<n and x>0:
            t=vessels[p][1]-vessels[p][0]
            if x>t:
                x-=t
                vessels[p][0]=vessels[p][1]
                tt.add(p)
                p=index[p]
            else:
                vessels[p][0]+=x
                break
        for i in tt:
            index[i]=p
    else:
        a,b=list(map(int,a.split()))
        ans.append(vessels[b-1][0])
print('\n'.join(map(str,ans)))

def command(cmd) :
    t=cmd[0]
    if t==1 :
        pour(cmd[1],cmd[2])
    else :
        amount(cmd[1])

def pour(p,amount) :
    Skip=[]
    while p<=n and amount>0:
        t=C[p-1]-W[p-1]
        if amount>=t :
            amount-=t
            W[p-1]=C[p-1]
            Skip.append(p)
        else :
            W[p-1]+=amount
            break
        p=Links[p]
    for i in Skip :
        Links[i]=p
        #print(W)
    
def amount(p) :
    P.append(W[p-1])

n=int(input())
C=list(map(int,input().split()))
W=[0]*n
Links=list(map(int,range(1,n+2)))
P=[]
m=int(input())
for i in range(m) :
    command([int(i) for i in input().split()])
for i in P :
    print(i)

n = int(input())
a = [int(i) for i in input().split()]
b = [0]*n

after = list(map(int,list(range(1,n+2))))
    
#print(a)

def add_water(p,x):
    i = p-1
    skip = []
    while x>0 and i<n:
        space = a[i]-b[i]
        if x >= space:
            x -= space
            b[i] = a[i]
            skip.append(i)
            i = after[i] 
        else:
            b[i] += x
            break

    for j in skip:
        after[j] = i

m = int(input())
P =[]
for i in range(m):
    l = [int(j) for j in input().split()]
    #print(l)
    if l[0] == 1:
        add_water(l[1],l[2])

    else:
        P.append(b[l[1]-1])

for j in P:
    print(j)


n=int(input());
nv=(n+2)*[0];
v=[int(i) for i in input().split()];
f=(n+2)*[0];
go = list(map(int,list(range(1,n+2))))
m=int(input());
p=[]
for i in range(m):
	c=[int(i) for i in input().split()];
	if c[0]==1 :
		k=c[1]-1;
		vv=c[2];
		kk=k;
		r=0;
		while((vv>0)and(kk<n)):
			if(vv<=v[kk]-nv[kk]):
				nv[kk]=nv[kk]+vv;
				vv=0;
				break;
			else:
				vv=vv-(v[kk]-nv[kk]);
				nv[kk]=v[kk];
				f[r]=kk;
				r=r+1;
				kk=go[kk];
		for j in range(r):
			go[f[j]]=kk;
			
	if c[0]==2:
		p.append(nv[c[1]-1]);
for i in p:
	print(i)


n=int(input());
water=(n+2)*[0];
vol=[int(i) for i in input().split()];
trace=(n+2)*[0];
next = [i+1 for i in range(n+2)];
m=int(input());
out=[]
for i in range(m):
	c=[int(i) for i in input().split()];
	if c[0]==1 :
		w=c[2];
		k=c[1]-1;
		r=0;
		while((w>0)and(k<n)):
			if(w<=vol[k]-water[k]):
				water[k]=water[k]+w;
				break;
			else:
				w=w-(vol[k]-water[k]);
				water[k]=vol[k];
				trace[r]=k;
				r=r+1;
				k=next[k];
		for j in range(r):
			next[trace[j]]=k;
	if c[0]==2:
		out.append(water[c[1]-1]);
for i in out:
	print(i)


n=int(input());
water=(n+2)*[0];
vol=[int(i) for i in input().split()];
trace=(n+2)*[0];
next = [i+1 for i in range(n+2)];
m=int(input());
out=[]
for i in range(m):
	c=[int(i) for i in input().split()];
	if c[0]==1 :
		w=c[2];
		k=c[1]-1;
		r=0;
		while((w>0)and(k<n)):
			if(w<=vol[k]-water[k]):
				water[k]=water[k]+w;
				break;
			else:
				w=w-(vol[k]-water[k]);
				water[k]=vol[k];
				trace[r]=k;
				r=r+1;
				k=next[k];
		for j in range(r):
			next[trace[j]]=k;
	if c[0]==2:
		out.append(water[c[1]-1]);
for i in out:
	print(i)




n=int(input())
a=[int(i) for i in input().split()]
v=[0]*n
m=int(input())
f=[i+1 for i in range(n)]
ans=[]
for i in range(m):
    q=[int(i) for i in input().split()]
    if q[0]==1:
        p,x=q[1],q[2]
        asdf=[]
        j=p-1
        while j<n:
            tmp=x+v[j]-a[j]
            if tmp<=0:
                v[j]+=x
                break
            else:
                x=tmp
                v[j]=a[j]
                asdf.append(j)
                j=f[j]
        for z in asdf:
            f[z]=j
    else:
        ans.append(v[q[1]-1])

for i in ans:
    print(i)


import copy
n=int(input())
ocu=[0]+list(map(int,input().split()))
V=dict()
for i in range(1,n+1):
    V[i]=ocu[i]
ocu=[0]*(n+1)
stream=[0]*(n+1)
l=0
ans=[]
for i in range(1,n):
    stream[i]=i+1
stream[n]=0
m=int(input())
for i in range(m):
    s=list(map(int,input().split()))
    if s[0]==1:
        x0,p=s[1],s[2]
        x=x0
        temp1=set()
        while True:
            if p<V[x]-ocu[x]:
                ocu[x]+=p
                break
            else:
                p-=V[x]-ocu[x]
                ocu[x]=V[x]
                temp1.add(x)
                x=stream[x]
                if x==0:break
        for a in temp1:
            stream[a]=x
    if s[0]==2:
        ans.append(ocu[s[1]])
print('\n'.join(map(str,ans)))


n = int(input())
a = list(map(int, input().split()))
m = int(input())
v = [0] * n
f = list(range(1, n + 1))
l = []
for i in range(m):
    q = list(map(int, input().split()))
    if q[0] == 1:
        p, x = q[1], q[2]
        u = []
        j = p - 1
        while j < n:
            z = x + v[j] - a[j]
            if z <= 0:
                v[j] += x
                break
            else:
                x = z
                v[j] = a[j]
                u.append(j)
                j = f[j]
        for z in u:
            f[z] = j
    else:
        l.append(v[q[1] - 1])

for i in l:
    print(i)


n = int(input())
a = list(map(int, input().split()))
m = int(input())
v = [0] * n
f = list(range(1, n + 1))
l = []
for i in range(m):
    q = list(map(int, input().split()))
    if q[0] == 1:
        p, x = q[1], q[2]
        u = []
        j = p - 1
        while j < n:
            z = x + v[j] - a[j]
            if z <= 0:
                v[j] += x
                break
            else:
                x = z
                v[j] = a[j]
                u.append(j)
                j = f[j]
        for z in u:
            f[z] = j
    else:
        l.append(v[q[1] - 1])

print(*l,sep='\n')


n = int(input())
vessel = [int(i) for i in input().split()]
water_amount = [0] * n
m = int(input())
next_vessel = [int(i) for i in range(1,n + 1)]
answer = []

for i in range(m):
    query = [int(j) for j in input().split()]
    
    if query[0] == 1:
        k = query[1] - 1
        skip_vessel = []
        while k < n:
            delta = vessel[k] - water_amount[k]
            if delta <= query[2]:
                water_amount[k] = vessel[k]
                query[2] -= delta
                skip_vessel.append(k)
                k = next_vessel[k]
            else:
                water_amount[k] += query[2]
                break
        for j in skip_vessel:
            next_vessel[j] = k
            
    else:
        answer.append(water_amount[query[1] - 1])

print(*answer, sep = '\n')


n = int(input())
vessel = [int(i) for i in input().split()]
water_amount = [0] * n
m = int(input())
next_vessel = [int(i) for i in range(1,n + 1)]
answer = []

for i in range(m):
    query = [int(j) for j in input().split()]
    
    if query[0] == 1:
        k = query[1] - 1
        skip_vessel = []
        while k < n:
            delta = vessel[k] - water_amount[k]
            if delta <= query[2]:
                water_amount[k] = vessel[k]
                query[2] -= delta
                skip_vessel.append(k)
                k = next_vessel[k]
            else:
                water_amount[k] += query[2]
                break
        for j in skip_vessel:
            next_vessel[j] = k
            
    else:
        answer.append(water_amount[query[1] - 1])

print(*answer, sep = '\n')


n=int(input())
a=[int(i) for i in input().split()]
v=[0]*n
m=int(input())
f=[i+1 for i in range(n)]
ans=[]
for i in range(m):
    q=[int(i) for i in input().split()]
    if q[0]==1:
        p,x=q[1],q[2]
        xyz=[]
        j=p-1
        while j<n:
            tmp=x+v[j]-a[j]
            if tmp<=0:
                v[j] = x+v[j]
                break
            else:
                x=tmp
                v[j]=a[j]
                xyz.append(j)
                j=f[j]
        for z in xyz:
            f[z]=j
    else:
        ans.append(v[q[1]-1])

for i in ans:
    print(i)

n=int(input())
a=[int(i) for i in input().split()]
v=[0]*n
m=int(input())
f=[i+1 for i in range(n)]
ans=[]
for i in range(m):
    q=[int(i) for i in input().split()]
    if q[0]==1:
        p,x=q[1],q[2]
        asdf=[]
        j=p-1
        while j<n:
            tmp=x+v[j]-a[j]
            if tmp<=0:
                v[j]+=x
                break
            else:
                x=tmp
                v[j]=a[j]
                asdf.append(j)
                j=f[j]
        for z in asdf:
            f[z]=j
    else:
        ans.append(v[q[1]-1])

for i in ans:
    print(i)


'''
Created on 2016-4-9

@author: chronocorax
'''

def line():
    return [int(c) for c in input().split()]

n = line()[0]
cap = line()
cap0 = cap[:]
nxt = [i + 1 for i in range(n)]

result = []

m = line()[0]
for _ in range(m):
    tup = line()
    if tup[0] == 1:
        p = tup[1] - 1
        p0 = p
        x = tup[2]
#         flush(p - 1, x)
        marker = []
        while p < n and cap[p] < x:
            x -= cap[p]
            cap[p] = 0
            marker.append(p)
            p = nxt[p]
        if p < n: cap[p] -= x
        for i in marker:
            nxt[i] = p
    else:
        k = tup[1]
        result.append(cap0[k - 1] - cap[k - 1])
    
for res in result:
    print(res)

n = int(input())
a = list(map(int, input().split()))
b = list(a)
f = [i+1 for i in range(n)]
def getf(x):
	y = x
	while x < n and a[x] == 0:
		x = f[x]
	while y < n and a[y] == 0:
		t = f[y]
		f[y], y = x, t
	return x
m = int(input())
ans = []
for i in range(m):
	tmp = list(map(int, input().split()))
	p = tmp[1]-1
	if tmp[0] == 1:
		x = tmp[2]
		l = []
		while p < n:
			if a[p] >= x:
				a[p] -= x
				break
			l.append(p)
			x -= a[p]
			a[p] = 0
			#p = getf(p)
			p = f[p]
		for x in l:
			f[x] = p
	else:
		ans.append(b[p] - a[p])
print('\n'.join(map(str, ans)))


n = int(input())
a = list(map(int, input().split()))
b = list(a)
f = [i+1 for i in range(n)]
def getf(x):
	y = x
	while x < n and a[x] == 0:
		x = f[x]
	while y < n and a[y] == 0:
		t = f[y]
		f[y], y = x, t
	return x
m = int(input())
ans = []
for i in range(m):
	tmp = list(map(int, input().split()))
	p = tmp[1]-1
	if tmp[0] == 1:
		x = tmp[2]
		l = []
		while p < n:
			if a[p] > x:
				a[p] -= x
				break
			l.append(p)
			x -= a[p]
			a[p] = 0
			p = getf(p)
		for x in l:
			f[x] = p
	else:
		ans.append(b[p] - a[p])
print('\n'.join(map(str, ans)))


n = int(input())
a = list(map(int, input().split()))
b = list(a)
f = [i+1 for i in range(n)]
def getf(x):
	y = x
	while x < n and a[x] == 0:
		x = f[x]
	while y < n and a[y] == 0:
		t = f[y]
		f[y], y = x, t
	return x
m = int(input())
ans = []
for i in range(m):
	tmp = list(map(int, input().split()))
	p = tmp[1]-1
	if tmp[0] == 1:
		x = tmp[2]
		while p < n:
			if a[p] > x:
				a[p] -= x
				break
			x -= a[p]
			a[p] = 0
			p = getf(p)
	else:
		ans.append(b[p] - a[p])
print('\n'.join(map(str, ans)))


n = int(input())
m = [int(i) for i in input().split()]
k = [0] * n
p = int(input())
l = list(range(1,n + 1))
j = []
for i in range(p):
    t = [int(i) for i in input().split()]

    if t[0] == 1:
        h = []
        a ,b= t[1] - 1,t[2]
        while b > 0 and a < n:
            if b <=m[a] - k[a]:
                k[a] += b
                break
            else:
                b = b -(m[a] - k[a])
                k[a] = m[a]
                h.append(a)
                a=l[a]
        for i in h:
            l[i] = a
    else:
        j.append(k[t[1] - 1])

print(*j,sep='\n')

o = int(input())
m = [int(i) for i in input().split()]
k = [0] * o
p = int(input())
l = list(range(1,o + 1))
j = []
for i in range(p):
    t = [int(i) for i in input().split()]

    if t[0] == 1:
        h = []
        a ,b= t[1] - 1,t[2]
        while b > 0 and a < o:
            if b <=m[a] - k[a]:
                k[a] += b
                break
            else:
                b = b -(m[a] - k[a])
                k[a] = m[a]
                h.append(a)
                a=l[a]
        for i in h:
            l[i] = a
    else:
        j.append(k[t[1] - 1])

print(*j,sep='\n')

n = int(input())
vessel = [int(i) for i in input().split()]
water_amount = [0] * n
m = int(input())
next_vessel = [int(i) for i in range(1,n + 1)]
answer = []

for i in range(m):
    query = [int(j) for j in input().split()]
    
    if query[0] == 1:
        k = query[1] - 1
        skip_vessel = []
        while k < n:
            delta = vessel[k] - water_amount[k]
            if delta <= query[2]:
                water_amount[k] = vessel[k]
                query[2] -= delta
                skip_vessel.append(k)
                k = next_vessel[k]
            else:
                water_amount[k] += query[2]
                break
        for j in skip_vessel:
            next_vessel[j] = k
            
    else:
        answer.append(water_amount[query[1] - 1])

print(*answer, sep = '\n')