Codeforces Round #416 (Div. 2) has been moved to start on 27.05.2017 09:05 (UTC).
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Vessels

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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.

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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/26/2017 04:49:27 (p1).

Desktop version, switch to mobile version.
User lists

Name |
---|