Задача 1. Чемпионат по устному счету

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Председатель жюри чемпионата по устному счету !A !B !C придумал новое задание для участников чемпионата. Исходно на доске выписывается n целых чисел: a1, a2, …, an. После этого участник должен выполнять команды двух типов:

  1. Стереть i-е число с доски и записать вместо него число x. То есть, если на доске были записаны числа a1, a2, …, an,~ то после выполнения команды числа будут равны: a1, …, ai − 1, x, ai + 1, …, an.

  2. Циклически сдвинуть последовательность чисел на k вправо. То есть, если на доске были записаны числа a1, a2, …, an, то после выполнения команды числа будут равны: an − k + 1, an − k + 2, …, an, a1, a2, …, an − k.

После выполнения каждой команды участник должен вычислить сумму всех чисел, записанных на доске, и сообщить ее жюри. Чтобы подготовиться проверять ответы участников, членам жюри необходимо самим вычислить требуемые суммы.

Формат входных данных

В первой строке записано целое число n — количество чисел, изначально записанных на доске (2 ≤ n ≤ 105).

Во второй строке через пробел записаны n целых чисел: a1, a2, …, an — числа, изначально выписанные на доске ( − 109 ≤ ai ≤ 109).

В третьей строке записано целое число q — количество команд, которые необходимо выполнить (1 ≤ q ≤ 105).

В каждой из следующих q строк записана очередная команда в следующем формате:

Формат выходных данных

В качестве ответа выведите q строк, в каждой из которых записано одно целое число.

В i-й строке должна быть записана сумма чисел на доске после выполнения первых i команд.

Обратите внимание, что ответ может быть достаточно большим и для его хранения потребуется 64-битный тип данных, int64 в паскале, long long в C++, long в Java.

Ограничения

2 ≤ n ≤ 105

 − 109 ≤ ai ≤ 109

1 ≤ q ≤ 105

1 ≤ i ≤ n;  − 109 ≤ x ≤ 109

1 ≤ k < n

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
1 22 2 ≤ n ≤ 1 000, есть только команды первого типа полная
2 17 2 ≤ n ≤ 1 000, во всех командах второго типа k = 1 полная
3 23 2 ≤ n ≤ 1 000 1, 2 полная
4 38 1 — 3 первая ошибка

Замечание

Рассмотрим пример из условия. Изначально последовательность записанных на доске чисел равна: 4,~1,~2,~1,~5,~3.

После первой команды последовательность циклически сдвигается на 3 элемента вправо. Новая последовательность: 1,~5,~3,~4,~1,~2. Сумма чисел равна: 1 + 5 + 3 + 4 + 1 + 2 = 16.

После второй команды необходимо заменить третий элемент последовательности на число 10. Новая последовательность: 1,~5,~10,~4,~1,~2. Сумма чисел равна: 1 + 5 + 10 + 4 + 1 + 2 = 23.

После третьей команды заменить четвертый элемент на число 4. Так как четвертый элемент уже равен 4, последовательность не изменяется. Сумма чисел также равна 23.

После четвертой команды последовательность циклически сдвигается на 1: 2,~1,~5,~10,~4,~1. Сумма чисел не изменилась.

Наконец, после пятой команды последовательность становится равна:  − 10,~1,~5,~10,~4,~1. Сумма чисел в итоговой последовательности равна  − 10 + 1 + 5 + 10 + 4 + 1 = 11.

Примеры тестов

Стандартный вход Стандартный выход
1
6
4 1 2 1 5 3
5
2 3
1 3 10
1 4 4
2 1
1 1 -10
16
23
23
23
11
2
3
1000000000 1000000000 1000000000
3
1 2 999999999
2 2
1 2 999999999
2999999999
2999999999
2999999998

0.176s 0.030s 15