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 赠送给你一个空数组。您可以对其执行三种类型的操作。
- 对数组执行循环移位。也就是说,数组 $$$[a_1, a_2, \ldots, a_n]$$$ 变为 $$$[a_n, a_1, a_2, \ldots, a_{n-1}].$$$
- 反转整个数组。也就是说,数组 $$$[a_1, a_2, \ldots, a_n]$$$ 变为 $$$[a_n, a_{n-1}, \ldots, a_1].$$$
- 将一个元素追加到数组末尾。将 $$$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$$$ 行,输出 每次操作后数组的 眩晕 数组的 。
示例
输入复制
1133 13 23 313 423 513 623 721
输出复制
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]$$$