P10086 [ROIR 2022] 口算比赛 (Day 1)

翻译自 [ROIR 2022 D1T1](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day1.pdf)。 在一个规则新奇的口算比赛中，评委在黑板上写下 $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$ 条指令后黑板上所有数字的总和。

样例 $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$。 本题使用捆绑测试。 | 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $22$ | $n\le1000$ 且所有指令都是第一类 | | $2$ | $17$ | $n\le1000$ 且所有第二类指令中 $k=1$ | | $3$ | $23$ | $n\le1000$ | | $4$ | $38$ | 无 | 对于 $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$。