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*<sub class="lower-index">*i*</sub> liters.

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:
 1.  Add *x*<sub class="lower-index">*i*</sub> liters of water to the *p*<sub class="lower-index">*i*</sub>-th vessel; 1.  Print the number of liters of water in the *k*<sub class="lower-index">*i*</sub>-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.
The first line contains integer *n* — the number of vessels (1 ≤ *n* ≤ 2·10<sup class="upper-index">5</sup>). The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> — the vessels' capacities (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>). 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<sup class="upper-index">5</sup>). Each of the next *m* lines contains the description of one query. The query of the first type is represented as "1 *p*<sub class="lower-index">*i*</sub> *x*<sub class="lower-index">*i*</sub>", the query of the second type is represented as "2 *k*<sub class="lower-index">*i*</sub>" (1 ≤ *p*<sub class="lower-index">*i*</sub> ≤ *n*, 1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>, 1 ≤ *k*<sub class="lower-index">*i*</sub> ≤ *n*).
#include <iostream>
#include <vector>


using namespace std;


int n, m;
vector<long long> a;
vector<long long> b;
vector<long long> nxt;


int add_water(int i, long long x) {
	if (i >= n) {
		return n;
	}
	else if (b[i] + x >= a[i]) {
		x -= a[i] - b[i];
		b[i] = a[i];
		int res = add_water(nxt[i], x);
		nxt[i] = res;
		return res;
	}
	else {
		b[i] += x;
		return i;
	}
}


long long get_water(int i) {
	return b[i];
}


int main() {
	cin >> n;
	a.resize(n);
	nxt.resize(n);
	b.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		nxt[i] = i + 1;
		b[i] = 0;
	}
	cin >> m;
	for (int i = 0; i < m; ++i) {
		int t;
		cin >> t;
		if (t == 1) {
			int p, x;
			cin >> p >> x;
			--p;
			add_water(p, x);
		}
		else if (t == 2) {
			int k;
			cin >> k;
			--k;
			cout << get_water(k) << "\n";
		}
	}
	return 0;
}

# Mon Oct 12 2020 09:04:07 GMT+0300 (Москва, стандартное время)
