Codeforces Round 218 (Div. 2) |
---|
Закончено |
Есть система из n сосудов, расположенных один над другим так, как показано на рисунке ниже. Представим, что сосуды пронумерованы числами от 1 до n в порядке от самого верхнего к самому нижнему, объем i-го сосуда равен ai литров.
Изначально все сосуды пустые. В некоторые сосуды наливают воду, при этом вся вода, не поместившаяся в i-й сосуд, переливается в (i + 1)-й. Жидкость, не поместившаяся в n-й сосуд, выливается на пол.
Ваша задача состоит в том, чтобы промоделировать наливание воды в сосуды. Для этого вам потребуется обрабатывать два типа запросов:
При ответе на второй запрос можно считать, что вся вода, налитая до этого момента, уже успела перелиться между сосудами.
В первой строке записано целое число n — количество сосудов (1 ≤ n ≤ 2·105). Во второй строке записаны n целых чисел a1, a2, ..., an — вместимости сосудов (1 ≤ ai ≤ 109). Вместимости сосудов не обязательно возрастают от верхних сосудов к нижним (см. второй пример). В третьей строке записано целое число m — количество запросов (1 ≤ m ≤ 2·105). Каждая из следующих m строк содержит описание одного запроса. Запрос первого типа задается как «1 pi xi», запрос второго типа — как «2 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
Название |
---|