Problem Background

Translated from ROIR 2022 D1T1.

In a novel mental arithmetic competition, judges write $n$ integers $a_1, a_2, \dots, a_n$ on the blackboard. Contestants are required to decide which of the following two types of instructions to execute:

1. Erase the $i$-th number and write the number $x$ in its place. That is, if the blackboard originally had the sequence $a_1, a_2, \dots, a_n$, after executing this instruction, the sequence becomes $a_1, \dots, a_{i-1}, x, a_{i+1}, \dots, a_n$.
2. Rotate the sequence of numbers to the right by $k$ positions. That is, if the blackboard originally had the sequence $a_1, a_2, \dots, a_n$, after executing this instruction, the sequence becomes $a_{n-k+1}, a_{n-k+2}, \dots, a_n, a_1, a_2, \dots, a_{n-k}$.

Problem Description

After each instruction is executed, contestants must report the sum of all numbers on the blackboard to the judges. To verify the contestants' answers, the judges need to calculate the sums themselves.

Input Format

The first line contains an integer $n$, representing the initial number of integers on the blackboard.

The second line contains $n$ integers separated by spaces, representing the initial integers $a_1, a_2, \dots, a_n$ written on the blackboard.

The third line contains an integer $q$, representing the number of instructions to be executed.

The next $q$ lines describe each instruction, formatted as follows:
- 1 i x: Indicates that the contestant replaces the $i$-th number with $x$.
- 2 k: Indicates that the contestant rotates the sequence of numbers to the right by $k$ positions.

Output Format

Output $q$ lines, each containing a single integer. The $i$-th line should contain the sum of all numbers on the blackboard after executing the first $i$ instructions.

Sample Input and Output

Sample Input #1

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

Sample Output #1

16
23
23
23
11

Sample Input #2

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

Sample Output #2

2999999999
2999999999
2999999998

Notes

Sample $1$ Explanation:

Initially, the sequence on the blackboard is: $4, 1, 2, 1, 5, 3$.

After executing the first instruction, the sequence is rotated right by $3$ positions. The new sequence is $1, 5, 3, 4, 1, 2$. The sum of all numbers is $1 + 5 + 3 + 4 + 1 + 2 = 16$.

After executing the second instruction, we replace the third element with $10$. The new sequence is $1, 5, 10, 4, 1, 2$. The sum of all numbers is $1 + 5 + 10 + 4 + 1 + 2 = 23$.

After executing the third instruction, we replace the fourth element with $4$. Since the fourth element is already $4$, the sequence does not change. The sum remains $23$.

After executing the fourth instruction, the sequence is rotated right by $1$ position, becoming $2, 1, 5, 10, 4, 1$, and the sum remains unchanged.

Finally, after executing the fifth instruction, the sequence becomes $-10, 1, 5, 10, 4, 1$. The final sum of the sequence is $-10 + 1 + 5 + 10 + 4 + 1 = 11$.

This problem uses bundled testing.

For $100\%$ of the data, $2 \le n \le 10^5$, $-10^9 \le a_i \le 10^9$, $1 \le q \le 10^5$. For the first-type instructions, $1 \le i \le n$. For the second-type instructions, $-10^9 \le x \le 10^9$, $1 \le k < n$.

见题面 Input 部分

见题面 Output 部分