题目背景

翻译自 ROIR 2022 D1T1。

在一个规则新奇的口算比赛中，评委在黑板上写下 $n$ 个整数 $a_1, a_2, \dots , a_n$。参赛选手需要自行决定执行以下两种类型的指令：

1. 擦除第 $i$ 个数字，并将数字 $x$ 写入该位置。也就是说，如果黑板上原本写着数字 $a_1, a_2, \dots , a_n$，那么执行该指令后，数字序列将变为 $a_1, \dots , a_{i−1}, x, a_{i+1}, \dots , a_n$。
2. 将数字序列循环右移 $k$ 位。也就是说，如果黑板上原本写着数字 $a_1, a_2, \dots , a_n$，那么执行该指令后，数字序列将变为 $a_{n−k+1}, a_{n−k+2}, \dots , a_n, a_1, a_2, \dots , a_{n−k}$。

题目描述

每次执行完指令后，参赛选手需要将黑板上所有数字的总和报告给评委会。为了检查参赛选手的答案，评委们需要自己计算总和。

输入格式

第一行包含一个整数 $n$，表示初始时黑板上的数字数量。

第二行包含 $n$ 个整数，通过空格分隔，表示初始时写在黑板上的数字 $a_1, a_2, \dots , a_n$。

第三行包含一个整数 $q$，表示需要执行的指令数量。

接下来的 $q$ 行中，每行描述一条指令，格式如下：

• 1 i x：表示参赛选手将第 $i$ 个数字替换为 $x$。
• 2 k：表示参赛选手将数字序列循环右移 $k$ 位。

输出格式

输出 $q$ 行，每行包含一个整数。第 $i$ 行应该包含执行前 $i$ 条指令后黑板上所有数字的总和。

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

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

2999999999
2999999999
2999999998

提示

样例 $1$ 解释：

初始时，在黑板上写有数字序列：$4, 1, 2, 1, 5, 3$。

在执行第一条指令后，数字序列向右循环移动了 $3$ 位。新的数字序列为 $1, 5, 3, 4, 1, 2$。所有数字的总和为 $1 + 5 + 3 + 4 + 1 + 2 = 16$。

在执行第二条指令后，我们需要将第三个元素替换为 $10$。新的数字序列为 $1, 5, 10, 4, 1, 2$。所有数字的总和为 $1 + 5 + 10 + 4 + 1 + 2 = 23$。

在执行第三条指令后，我们需要将第四个元素替换为 $4$。由于第四个元素已经是 $4$，数字序列没有发生改变。所有数字的总和仍然是 $23$。

在执行第四条指令后，数字序列向右循环移动了 $1$ 位，变为 $2, 1, 5, 10, 4, 1$，总和不变。

最后，在执行第五条指令后，数字序列变为 $-10, 1, 5, 10, 4, 1$。最终数字序列的总和为 $-10 + 1 + 5 + 10 + 4 + 1 = 11$。

本题使用捆绑测试。

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$−10^9 \le a_i \le 10^9$，$1 \le q \le 10^5$。对于第一类指令，$1 \le i \le n$。对于第二类指令，$−10^9 \le x \le 10^9$，$1 \le k < n$。