题目描述

对于长度为 $m$ 的数组 $b$，定义它的权值为

初始给定一个空数组，你需要依次执行 $q$ 次操作：

• 1：对数组做一次循环右移，即 $[a_1,a_2,\ldots,a_n]$ 变为 $[a_n,a_1,a_2,\ldots,a_{n-1}]$；
• 2：翻转整个数组；
• 3 k：在数组末尾加入元素 $k$。

每次操作后，输出当前数组的权值。所有操作都会永久修改数组。

输入格式

第一行包含整数 $t$，表示测试组数。

每组测试数据第一行包含整数 $q$。接下来 $q$ 行描述操作。保证每组测试数据的第一次操作一定是 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

数据范围

• $1 \le t \le 10^4$
• $1 \le q \le 2\cdot 10^5$
• $1 \le k \le 10^6$
• 所有测试组的 $q$ 之和不超过 $2\cdot 10^5$

来源

Codeforces Round 1017 (Div. 4), Problem G - Chimpanzini Bananini