Chimpanzini Bananini 的数组操作

问题描述

Chimpanzini Bananini 正站在一场决定性的战斗边缘——这场战斗注定带来终局。

对于一个长度为 $m$ 的任意数组 $b$，我们定义该数组的 rizziness 为 $\sum_{i=1}^m b_i \cdot i = b_1 \cdot 1 + b_2 \cdot 2 + b_3 \cdot 3 + \ldots + b_m \cdot m$。

Chimpanzini Bananini 送给你一个空数组。你可以对它进行以下三类操作：

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. 在数组末尾追加一个元素。将 $k$ 追加到数组末尾后，数组 $[a_1, a_2, \ldots, a_n]$ 变为 $[a_1, a_2, \ldots, a_n, k]$。

在每次操作之后，你都希望计算当前数组的 rizziness。

注意所有操作都是持久的。这意味着每次操作都会修改数组，后续操作应当基于前序操作执行后的当前数组状态进行。

输入格式

第一行包含一个整数 $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$。

输出格式

对于每个操作，输出操作后数组的 rizziness。

样例说明

数组的前六个状态：

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

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