Background

Translated from ROIR 2022 D1T1。

In a mental arithmetic contest with unusual rules, the judges write $n$ integers $a_1, a_2, \dots , a_n$ on the blackboard. The contestant needs to decide by themselves to execute the following two types of operations:

1. Erase the $i$-th number and write the number $x$ in that position. That is, if the blackboard originally shows $a_1, a_2, \dots , a_n$, then after this operation the sequence becomes $a_1, \dots , a_{i−1}, x, a_{i+1}, \dots , a_n$。
2. Cyclically shift the sequence to the right by $k$ positions. That is, if the blackboard originally shows $a_1, a_2, \dots , a_n$, then after this operation 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 operation, the contestant must report to the jury the sum of all numbers currently on the blackboard. To verify the contestant’s answers, the judges need to compute these sums themselves。

Input Format

The first line contains an integer $n$, the number of numbers on the blackboard at the beginning。

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

The third line contains an integer $q$, the number of operations to be performed。

In the next $q$ lines, each line describes one operation in the following format:

• 1 i x: the contestant replaces the $i$-th number with $x$。
• 2 k: the contestant cyclically shifts the sequence to the right by $k$ positions。

Output Format

Output $q$ lines, each containing one integer. The $i$-th line should contain the sum of all numbers on the blackboard after performing the first $i$ operations。

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

Hint

Explanation of Sample $1$:

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

After the first operation, the sequence is cyclically shifted to the 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 the second operation, 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 the third operation, we replace the fourth element with $4$。Since the fourth element is already $4$, the sequence does not change. The sum is still $23$。

After the fourth operation, the sequence is cyclically shifted to the right by $1$ position and becomes $2, 1, 5, 10, 4, 1$，and the sum does not change。

Finally, after the fifth operation, 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 testdata。

Constraints: 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 of operation, $1 \le i \le n$。For the second type of operation, $−10^9 \le x \le 10^9$, $1 \le k < n$。

Translated by ChatGPT 5