Triple Products

A teacher wants to test the class's arithmetic fluency. Define a triple product as the product of three numbers taken from three distinct positions.

The teacher writes a row of $n$ natural numbers on the board. Over time the teacher either replaces one of the numbers with another natural number, or asks for the sum of all triple products that can be formed from the numbers in a given segment of the board. What makes a choice distinct is position, not value: two chosen numbers may be equal in value, but they must sit at different positions.

Answer every such query.

The first line contains the number of test cases $Z$ (here $Z = 1$).

Each test case is given as follows.

• A line with a natural number $n$ ($1 \le n \le 200000$).
• A line with $n$ natural numbers separated by spaces, the initial numbers on the board.
• A line with a natural number $q$ ($1 \le q \le 200000$), the number of operations.
• $q$ lines, each describing one operation:
  • Z a b ($1 \le a \le n$, $b > 0$): replace the number at position $a$ with the natural number $b$.
  • Q a b ($1 \le a \le b \le n$): report the sum of all triple products formed from the numbers at positions in the range $[a, b]$.

At every moment the sum of all numbers on the board does not exceed one million ($10^6$).

For each Q operation, print on its own line a single natural number: the sum of all triple products that can be formed by choosing three distinct positions in the queried range.

For the board $[1, 3, 2, 2]$ the first query over $[1, 4]$ is $1\cdot3\cdot2 + 1\cdot3\cdot2 + 1\cdot2\cdot2 + 3\cdot2\cdot2 = 28.$ The second query covers only two numbers, so no triple can be formed and the answer is $0$. After the number at position $1$ is replaced by $2$, the board becomes $[2, 3, 2, 2]$ and the third query over $[1, 3]$ is $2\cdot3\cdot2 = 12$.