题目描述

译自 ROI Regional 2022 Day1 T1. Чемпионат по устному счету

口算比赛的评委为参赛者设计了一个新任务。最初，黑板上写有 $n$ 个整数：$a_1, a_2, \ldots, a_n$。接下来，参赛者需要执行两种类型的命令：

1. 擦除第 $i$ 个数并用数 $x$ 替换它。也就是说，如果黑板上原本写的是 $a_1, a_2, \ldots, a_n$，执行命令后，数字变为：$a_1, \ldots, a_{i - 1}, x, a_{i + 1}, \ldots, a_n$。
2. 将序列循环右移 $k$ 位。也就是说，如果黑板上原本写的是 $a_1, a_2, \ldots, a_n$，执行命令后，数字变为：$a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n, a_1, a_2, \ldots, a_{n - k}$。

每次执行命令后，参赛者需要计算黑板上所有数字的总和，并将结果报告给评委。为了准备检查参赛者的答案，评委们需要自己计算这些总和。

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 10^5)$，表示黑板上最初写的数字个数。

第二行包含 $n$ 个整数：$a_1, a_2, \ldots, a_n$ $(-10^9 \leq a_i \leq 10^9)$，表示最初写在黑板上的数字。

第三行包含一个整数 $q$ $(1 \leq q \leq 10^5)$，表示需要执行的命令数量。

接下来的 $q$ 行中，每行表示一个命令，格式如下：

• 1 i x 表示参赛者需要将序列中的第 $i$ $(1 \leq i \leq n)$ 个数替换为 $x$ $(-10^9 \leq x \leq 10^9)$。
• 2 k 表示参赛者需要将序列循环右移 $k$ $(1 \leq k < n)$ 位。

输出格式

输出 $q$ 行，每行一个整数，表示执行前 $i$ 条命令后黑板上数字的总和。

请注意，答案可能非常大，需要使用 64 位数据类型来存储，例如 Pascal 中的 int64，C++ 中的 long long，Java 中的 long。

6
4 1 2 1 5 3
5
2 3
1 3 10
1 4 4
2 1
1 1 -10

16
23
23
23
11

最初黑板上的数字序列为：$4, 1, 2, 1, 5, 3$。

1. 第一条命令将序列循环右移 $3$ 位。新的序列为：$1, 5, 3, 4, 1, 2$。数字总和为：$1 + 5 + 3 + 4 + 1 + 2 = 16$。
2. 第二条命令将序列中的第三个数替换为 $10$。新的序列为：$1, 5, 10, 4, 1, 2$。数字总和为：$1 + 5 + 10 + 4 + 1 + 2 = 23$。
3. 第三条命令将序列中的第四个数替换为 $4$。由于第四个数已经是 $4$，序列不变。数字总和仍为 $23$。
4. 第四条命令将序列循环右移 $1$ 位。新的序列为：$2, 1, 5, 10, 4, 1$。数字总和不变。
5. 第五条命令将序列中的第一个数替换为 $-10$。新的序列为：$-10, 1, 5, 10, 4, 1$。数字总和为：$-10 + 1 + 5 + 10 + 4 + 1 = 11$。

3
1000000000 1000000000 1000000000
3
1 2 999999999
2 2
1 2 999999999

2999999999
2999999999
2999999998

数据范围与提示

详细子任务附加限制及分值如下表所示。