D2. Minimum with Left Shift (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of this problem. In this version, you need to answer multiple queries.

Wuhudsm got irritated because Sanjay kept proposing too many questions to him. So Wuhudsm decided to give Sanjay a tough question. Wuhudsm told Sanjay that he cannot ask any more questions until he solves this one. Since he had no friends, he handed it over to you. Please solve it for him.

Given an array $$$a$$$ of length $$$n$$$, the cost $$$c$$$ is defined as:

$$$$$$ c = a_1 \cdot 1 + a_2 \cdot 2 + \dots + a_{n} \cdot n $$$$$$

You are given $$$q$$$ queries of two types:

  • 1 p x — Set the value of $$$ a_p$$$ to $$$x $$$.
  • 2 k — Find the cost if the array is shifted left cyclically exactly $$$k$$$ times. Note: we do not actually perform any shift operation on this array.

A left cyclic shift operation moves each element of the array one position to the left, with the first element moving to the end.

For example, $$$$$$ a = [1, 2, 3, 4] \quad$$$$$$ after one left shift becomes $$$$$$a = [2, 3, 4, 1] $$$$$$

Input
  • The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the size of the array.
    • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$ — the elements of the array.
    • The third line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of queries.
    • Then $$$q$$$ lines follow. The $$$i$$$-th line contains the $$$i$$$-th query is given either as
      • 1 p x $$$(1 \leq p \leq n, -10^9 \leq x \leq 10^9)$$$
      • 2 k $$$(0 \leq k \leq 10^9) $$$

    The sum of $$$n$$$ and $$$q$$$ across all test cases does not exceed $$$10^5$$$.

Output

For each query of type $$$2$$$, print the answer to this query in a new line.

Example
Input
2
4
1 2 3 4
3
2 2
1 1 5
2 3
3
1 -1 1
3
2 2
1 3 -1000000000
2 1000000000
Output
22
32
0
-1999999998
Note

In the first query of the first test case, if the array $$$a$$$ is left shifted $$$2$$$ times, $$$a=[3, 4, 1, 2]$$$.

We get $$$ c = 3 \cdot 1 + 4 \cdot 2 + 1 \cdot 3 + 2 \cdot 4 = 3 + 8 + 3 + 8 = 22 $$$.