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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Implementation

Spanning trees


Solutions:
from sys import stdin, setrecursionlimit
import math
from collections import defaultdict, deque
setrecursionlimit(15000)

def process_query(node, x, max_capacity, cur_capacity, link):
	i = node
	while link[i] != n + 1 and x > 0:
		if cur_capacity[link[i]] + x < max_capacity[link[i]]:
			cur_capacity[link[i]] += x
			break
		diff = max_capacity[link[i]] - cur_capacity[link[i]]
		cur_capacity[link[i]] = max_capacity[link[i]]
		x -= diff
		link[i] = link[i + 1]
		i = link[i]
	link[node] = link[i]

def convert_to_dict(max_capacity):
	(mydict1, mydict2) = (dict(), dict())
	link = dict()
	for i in range(len(max_capacity)):
		mydict1[i + 1] = max_capacity[i]
		mydict2[i + 1] = 0
		link[i + 1] = i + 1
	mydict1[len(max_capacity) + 1] = float('inf')
	mydict2[len(max_capacity) + 1] = float('inf')
	link[len(max_capacity) + 1] = len(max_capacity) + 1
	return (mydict1, mydict2, link)
n = int(stdin.readline().strip())
max_capacity = list(map(int, stdin.readline().split()))
(max_capacity, cur_capacity, link) = convert_to_dict(max_capacity)
m = int(stdin.readline().strip())
for _ in range(m):
	query = list(map(int, stdin.readline().split()))
	if len(query) == 3:
		process_query(query[1], query[2], max_capacity, cur_capacity, link)
	else:
		print(cur_capacity[query[1]])


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

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 = 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 = [int(i) for i in input().split()]
b = [0] * n
after = list(map(int, range(1, n + 2)))

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()]
	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())
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())
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)


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())
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')


from sys import stdin, stdout

def find_next(v):
	q = v
	while indexes[q] != q:
		q = indexes[q]
	while v != q:
		(indexes[v], v) = (q, indexes[v])
	return v
input = stdin.readline
n = int(input())
a = tuple(map(int, input().split()))
indexes = [i for i in range(n + 1)]
res = [0] * (n + 1)
for _ in range(int(input())):
	req = input().split()
	if req[0] == '1':
		(p, x) = (int(req[1]), int(req[2]))
		p -= 1
		while p < n and res[p] + x >= a[p]:
			x = res[p] + x - a[p]
			res[p] = a[p]
			f = 3
			b = 3
			c = 2
			f = b
			b = f = c
			indexes[p] = p = find_next(p + 1)
		res[p] += x
	else:
		k = int(req[1])
		stdout.write(f'{res[k - 1]}\n')


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()) + 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)))


def get_next_av(next_av, p):
	q = p
	while next_av[q] != q:
		q = next_av[q]
	while p != q:
		(next_av[p], p) = (q, next_av[p])
	return p

def main():
	from array import array
	from sys import stdin
	input = stdin.readline
	n = int(input())
	a = tuple(map(int, input().split()))
	next_av = array('i', range(n + 1))
	res = array('q', [0] * (n + 1))
	for _ in range(int(input())):
		inp = input()
		if inp.startswith('1'):
			(_2, p, x) = map(int, inp.split())
			p -= 1
			while p < n and res[p] + x >= a[p]:
				x = res[p] + x - a[p]
				res[p] = a[p]
				next_av[p] = p = get_next_av(next_av, p + 1)
			res[p] += x
		else:
			(_3, k) = map(int, inp.split())
			print(res[k - 1])
main()


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)


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 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]
		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())
m = list(map(int, input().split()))
k = [0] * n
p = int(input())
l = list((i + 1 for i in range(n)))
j = []
for i in range(p):
	t = list(map(int, 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 y in h:
			l[y] = a
	else:
		j.append(k[t[1] - 1])
print(' '.join(list((str(i) for i in j))))


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')


from sys import stdin, stdout
n = int(stdin.readline()) + 1
a = list(map(int, stdin.readline().split())) + [1 << 50]
(l, p, r) = ([0] * n, list(range(n)), [])
for i in range(int(stdin.readline())):
	t = list(map(int, stdin.readline().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
stdout.write('\n'.join(map(str, r)))