← 返回题目列表

Codeforces · 2094/G

G. 黑猩猩 巴纳尼尼

中文机器翻译题面 查看原题

Chimpanzini Bananini 正处于一场重大战斗的边缘——一场注定会带来结局的战斗。

对于长度为 $$$m$$$ 的任意数组 $$$b$$$,让我们表示 眩晕 数组的 为 $$$\sum_{i=1}^mb_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]$$$。

每次操作后,您有兴趣计算 数组的 眩晕 数组的 。

请注意,所有操作都是 执着。这意味着每个操作都会修改数组,并且后续操作应在前一个操作之后应用于数组的当前状态。

输入

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