G. Шимпанзини Бананини
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Шимпанзини Бананини стоит на пороге судьбоносной битвы — последней, где решится всё.

Для произвольного массива $$$b$$$ длины $$$m$$$ обозначим риззинесс массива как $$$\sum_{i=1}^mb_i\cdot i=b_1\cdot 1+b_2\cdot 2+b_3\cdot 3+\ldots + b_m\cdot m$$$.

Шимпанзини Бананини дарит вам пустой массив. Существует три типа операций, которые вы можете выполнить над ним.

  1. Выполнить циклический сдвиг массива. То есть, массив $$$[a_1, a_2, \ldots, a_n]$$$ становится $$$[a_n, a_1, a_2, \ldots, a_{n-1}].$$$
  2. Развернуть весь массив. То есть, массив $$$[a_1, a_2, \ldots, a_n]$$$ становится $$$[a_n, a_{n-1}, \ldots, a_1].$$$
  3. Добавить элемент в конец массива. Массив $$$[a_1, a_2, \ldots, a_n]$$$ становится $$$[a_1, a_2, \ldots, a_n, k]$$$ после добавления $$$k$$$ в конец массива.

После каждой операции вас интересует вычисление риззинесса вашего массива.

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

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит целое число $$$q$$$ ($$$1 \leq q \leq 2\cdot 10^5$$$) — количество операций, которые вы выполняете над своим массивом.

Следующие $$$q$$$ строк сначала содержат одно целое число $$$s$$$ ($$$1 \leq s \leq 3$$$) — тип операции.

  • Если $$$s=1$$$, то должна быть выполнена операция циклического сдвига.
  • Если $$$s=2$$$, то должна быть выполнена операция разворота.
  • Если $$$s=3$$$, то строка будет содержать дополнительное целое число $$$k$$$ ($$$1 \leq k \leq 10^6$$$), обозначающее элемент, добавляемый в конец массива.

Гарантируется, что сумма $$$q$$$ не превысит $$$2\cdot 10^5$$$ по всем наборам входных данных. Кроме того, гарантируется, что первая операция в каждом наборе входных данных будет с $$$s=3$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ строк, выводя риззинесс вашего массива после каждой операции.

Пример
Входные данные
1
13
3 1
3 2
3 3
1
3 4
2
3 5
1
3 6
2
3 7
2
1
Выходные данные
1
5
14
11
27
23
48
38
74
73
122
102
88
Примечание

Первые шесть состояний массива:

  • $$$[1]$$$
  • $$$[1, 2]$$$
  • $$$[1, 2, 3]$$$
  • $$$[3, 1, 2]$$$
  • $$$[3, 1, 2, 4]$$$
  • $$$[4, 2, 1, 3]$$$