D. Сосуды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Есть система из n сосудов, расположенных один над другим так, как показано на рисунке ниже. Представим, что сосуды пронумерованы числами от 1 до n в порядке от самого верхнего к самому нижнему, объем i-го сосуда равен ai литров.

Изначально все сосуды пустые. В некоторые сосуды наливают воду, при этом вся вода, не поместившаяся в i-й сосуд, переливается в (i + 1)-й. Жидкость, не поместившаяся в n-й сосуд, выливается на пол.

Ваша задача состоит в том, чтобы промоделировать наливание воды в сосуды. Для этого вам потребуется обрабатывать два типа запросов:

  1. Долить в pi-й сосуд xi литров воды;
  2. Вывести, сколько воды находится в ki-м сосуде.

При ответе на второй запрос можно считать, что вся вода, налитая до этого момента, уже успела перелиться между сосудами.

Входные данные

В первой строке записано целое число n — количество сосудов (1 ≤ n ≤ 2·105). Во второй строке записаны n целых чисел a1, a2, ..., an — вместимости сосудов (1 ≤ ai ≤ 109). Вместимости сосудов не обязательно возрастают от верхних сосудов к нижним (см. второй пример). В третьей строке записано целое число m — количество запросов (1 ≤ m ≤ 2·105). Каждая из следующих m строк содержит описание одного запроса. Запрос первого типа задается как «pi xi», запрос второго типа — как «ki» (1 ≤ pi ≤ n, 1 ≤ xi ≤ 109, 1 ≤ ki ≤ n).

Выходные данные

На каждый запрос второго типа в отдельной строке выведите количество воды в соответствующем сосуде.

Примеры
Входные данные
2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2
Выходные данные
4
5
8
Входные данные
3
5 10 8
6
1 1 12
2 2
1 1 6
1 3 2
2 2
2 3
Выходные данные
7
10
5