Чемпионат по устному счету

Председатель жюри чемпионата по устному счету !A !B !C придумал новое задание для участников чемпионата. Исходно на доске выписывается $n$ целых чисел: $a\_1, a\_2, \ldots, a\_n$. После этого участник должен выполнять команды двух типов:

1. Стереть $i$-е число с доски и записать вместо него число $x$. То есть, если на доске были записаны числа $a\_1, a\_2, \ldots, a\_n$, то после выполнения команды числа будут равны: $a\_1, \ldots, a\_{i - 1}, x, a\_{i + 1}, \ldots, a\_n$.
2. Циклически сдвинуть последовательность чисел на $k$ вправо. То есть, если на доске были записаны числа $a\_1, a\_2, \ldots, a\_n$, то после выполнения команды числа будут равны: $a\_{n - k + 1}, a\_{n - k + 2}, \ldots, a\_n, a\_1, a\_2, \ldots, a\_{n - k}$.

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

В первой строке записано целое число $n$ --- количество чисел, изначально записанных на доске ($2 \leq n \leq 10^5$).

Во второй строке через пробел записаны $n$ целых чисел: $a\_1, a\_2, \ldots, a\_n$ --- числа, изначально выписанные на доске ($-10^9 \leq a\_i \leq 10^9$).

В третьей строке записано целое число $q$ --- количество команд, которые необходимо выполнить ($1 \leq q \leq 10^5$).

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

• $1 i x$ --- это означает, что участник должен заменить $i$-е число последовательности на число $x$ ($1 \leq i \leq n$; $-10^9 \leq x \leq 10^9$).
• $2 k$ --- это означает, что участник должен циклически сдвинуть последовательность чисел на $k$ вправо ($1 \leq k < n$).

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

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

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

Рассмотрим пример из условия. Изначально последовательность записанных на доске чисел равна: $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$.