给你一个由 $5n$ 个整数组成的序列 $A_1, A_2, \dots, A_{5n}$。同时给你一个包含三种类型操作的查询序列：

1. “? $x$ $y$” 其中 $x$ 和 $y$ 是满足 $1 \le x \le y \le 5n$ 的整数。求位置从 $x$ 到 $y$（含）的元素之和：$A_x + A_{x+1} + \dots + A_y$。
2. “< $x$” 其中 $x$ 是满足 $1 \le x \le 5n - 1$ 的整数。将序列循环左移 $x$ 次，即将序列 $A$ 替换为序列 $A_{x+1}, A_{x+2}, \dots, A_{5n}, A_1, \dots, A_x$。
3. “# $P$” 其中 $P$ 是一个长度为 5 的排列。将序列分割成连续的 5 元素片段，并对每个片段应用排列 $P$。每个片段 $A_{5k+1}, \dots, A_{5k+5}$ 将被替换为 $A_{5k+P_1}, \dots, A_{5k+P_5}$。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^4$)。

第二行包含 $5n$ 个整数 $A_i$ ($|A_i| \le 10^4$)。

第三行包含一个整数 $m$ ($0 \le m \le 10^5$)，表示查询的数量。接下来的 $m$ 行包含上述格式的查询。

输出格式

对于每个 “?” 查询，单独在一行中输出其对应的和。

样例

样例输入 1

2
1 2 3 4 5 6 7 8 9 10
10
? 1 10
< 3
? 2 6
# 3 1 2 5 4
? 3 4
? 5 5
< 8
? 2 9
# 5 4 3 2 1
? 5 6

样例输出 1

55
35
13
7
42
13