Горы мусора
(Время: 1 сек. Память: 32 Мб Сложность: 26%)
Недавно Виталя во время прогулки шел мимо свалки и заметил, что мусор на ней сортируется на n типов. Каждый из типов мусора лежит в своей куче, и изначально в i-й куче находится ai единиц мусора. Виталя заметил, что когда мусора становится так много, что его видно из-за забора, то это уже не куча мусора, а целая гора! Такая ситуация происходит, когда в куче присутствует хотя бы m единиц мусора.
Виталя узнал расписание мусоровозов и знает все операции изменения куч мусора: это может быть как привоз, так и отвоз некоторого количества мусора из одной кучи.
Поскольку Виталя любит математику, ему интересно, какое суммарное количество мусора будет находиться в горах мусора после каждой операции изменения, но так как сам не любит считать, он попросил вас помочь ему с вычислением суммы гор.
Входные данные
В первой строке входного файла INPUT.TXT содержатся два целых числа n и m (1 ≤ n ≤ 2×105; 1 ≤ m ≤ 109) – количество типов мусора и минимальное количество мусора в горе соответственно.
Во второй строке содержатся n целых чисел ai (1 ≤ ai ≤ 109) – начальные размеры куч мусора.
В третьей строке содержится целое число k (1 ≤ k ≤ 2×105) – количество операций изменения.
В каждой из следующих k строк содержатся два целых числа t и x (1 ≤ t ≤ n; −109 ≤ x ≤ 109) – тип мусора и изменение количества мусора этого типа соответственно.
Гарантируется, что после каждой операции в каждой куче будет содержаться неотрицательное количество мусора.
Выходные данные
В выходной файл OUTPUT.TXT после каждой операции изменения в отдельную строку выведите сумму гор мусора на текущий момент.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 4
1 2 3 4 5
2
1 2
5 -3 | 9
4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
