#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
mt19937_64 randGen(system_clock().now().time_since_epoch().count());
mt19937 rnd(42);
const int N = 2e5 + 10;
struct Tree {
  vector<long long> t;
  int n;
  set<int> ids;
  void init(int sn) {
    n = sn;
    t.assign(4 * n, 0LL);
  }
  void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
      t[v] = a[tl];
      ids.insert(tl);
    } else {
      int mid = (tl + tr) / 2;
      build(a, v * 2, tl, mid);
      build(a, v * 2 + 1, mid + 1, tr);
      t[v] = t[v * 2] + t[v * 2 + 1];
    }
  }
  long long sum(int v, int tl, int tr, int l, int r) {
    if (l > r) {
      return 0LL;
    }
    if (l == tl && r == tr) {
      return t[v];
    }
    int mid = (tl + tr) / 2;
    return sum(v * 2, tl, mid, l, min(r, mid)) +
           sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
  }
  void upd(int v, int tl, int tr, int id, int val) {
    if (tl == tr) {
      t[v] = val;
    } else {
      int mid = (tl + tr) / 2;
      if (id <= mid) {
        upd(v * 2, tl, mid, id, val);
      } else {
        upd(v * 2 + 1, mid + 1, tr, id, val);
      }
      t[v] = t[v * 2] + t[v * 2 + 1];
    }
  }
  void rem(int l, int r) {
    auto efrom = ids.lower_bound(l);
    auto eto = ids.upper_bound(r);
    auto lcopy = efrom;
    while (lcopy != eto) {
      upd(1, 1, n, *lcopy, 0LL);
      ++lcopy;
    }
    ids.erase(efrom, eto);
  }
  void pour(int id, int val) {
    int l = id, r = n;
    int to = n;
    while (l <= r) {
      int mid = (l + r) / 2;
      long long can = sum(1, 1, n, id, mid);
      if (can >= val) {
        to = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    long long left = sum(1, 1, n, id, to - 1);
    long long sright = sum(1, 1, n, to, to);
    rem(id, to);
    if (sright > (val - left)) {
      upd(1, 1, n, to, sright - val + left);
      ids.insert(to);
    }
  }
};
struct Solver {
  Tree tree;
  void solve() {
    int n, m, a[N] = {};
    int l, r, q;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    tree.init(n);
    tree.build(a, 1, 1, n);
    cin >> m;
    while (m--) {
      cin >> l >> r;
      if (l == 1) {
        cin >> q;
        tree.pour(r, q);
      } else {
        cout << a[r] - tree.sum(1, 1, n, r, r) << "\n";
      }
    }
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  Solver sol;
  sol.solve();
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

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 ai 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:

  1. Add xi liters of water to the pi-th vessel; 
  2. Print the number of liters of water in the ki-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·105). The second line contains n integers a1, a2, ..., an — the vessels' capacities (1 ≤ ai ≤ 109). 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·105). Each of the next m lines contains the description of one query. The query of the first type is represented as "1 pi xi", the query of the second type is represented as "2 ki" (1 ≤ pi ≤ n, 1 ≤ xi ≤ 109, 1 ≤ ki ≤ 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
mt19937_64 randGen(system_clock().now().time_since_epoch().count());
mt19937 rnd(42);
const int N = 2e5 + 10;
struct Tree {
  vector<long long> t;
  int n;
  set<int> ids;
  void init(int sn) {
    n = sn;
    t.assign(4 * n, 0LL);
  }
  void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
      t[v] = a[tl];
      ids.insert(tl);
    } else {
      int mid = (tl + tr) / 2;
      build(a, v * 2, tl, mid);
      build(a, v * 2 + 1, mid + 1, tr);
      t[v] = t[v * 2] + t[v * 2 + 1];
    }
  }
  long long sum(int v, int tl, int tr, int l, int r) {
    if (l > r) {
      return 0LL;
    }
    if (l == tl && r == tr) {
      return t[v];
    }
    int mid = (tl + tr) / 2;
    return sum(v * 2, tl, mid, l, min(r, mid)) +
           sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
  }
  void upd(int v, int tl, int tr, int id, int val) {
    if (tl == tr) {
      t[v] = val;
    } else {
      int mid = (tl + tr) / 2;
      if (id <= mid) {
        upd(v * 2, tl, mid, id, val);
      } else {
        upd(v * 2 + 1, mid + 1, tr, id, val);
      }
      t[v] = t[v * 2] + t[v * 2 + 1];
    }
  }
  void rem(int l, int r) {
    auto efrom = ids.lower_bound(l);
    auto eto = ids.upper_bound(r);
    auto lcopy = efrom;
    while (lcopy != eto) {
      upd(1, 1, n, *lcopy, 0LL);
      ++lcopy;
    }
    ids.erase(efrom, eto);
  }
  void pour(int id, int val) {
    int l = id, r = n;
    int to = n;
    while (l <= r) {
      int mid = (l + r) / 2;
      long long can = sum(1, 1, n, id, mid);
      if (can >= val) {
        to = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    long long left = sum(1, 1, n, id, to - 1);
    long long sright = sum(1, 1, n, to, to);
    rem(id, to);
    if (sright > (val - left)) {
      upd(1, 1, n, to, sright - val + left);
      ids.insert(to);
    }
  }
};
struct Solver {
  Tree tree;
  void solve() {
    int n, m, a[N] = {};
    int l, r, q;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    tree.init(n);
    tree.build(a, 1, 1, n);
    cin >> m;
    while (m--) {
      cin >> l >> r;
      if (l == 1) {
        cin >> q;
        tree.pour(r, q);
      } else {
        cout << a[r] - tree.sum(1, 1, n, r, r) << "\n";
      }
    }
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  Solver sol;
  sol.solve();
  return 0;
}

```