# [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

### 样例输入 #1

```
6
4 1 2 1 5 3
5
2 3
1 3 10
1 4 4
2 1
1 1 -10
```

### 样例输出 #1

```
16
23
23
23
11
```

## 样例 #2

### 样例输入 #2

```
3
1000000000 1000000000 1000000000
3
1 2 999999999
2 2
1 2 999999999
```

### 样例输出 #2

```
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$。

本题使用捆绑测试。

| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $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$。