Председатель жюри чемпионата по устному счету !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.

Подзадачи