Integral of Polynomial Functions and Queries

A sequence $A_0, A_1, A_2, \cdots, A_N$ of length $N + 1$ is given. Then $N$ polynomial functions $f_1(x), f_2(x), f_3(x), \cdots, f_N(x)$ and a function $g(x)$ are determined by the following conditions.

• For every nonnegative integer $n$ with $n \le N$, $g(n) = A_n$.
• For every positive integer $n$ with $n \le N$, if $n - 1 \le x \le n$, then $g(x) = f_n(x)$.
• $g(x)$ is differentiable on the interval $(0, N)$.
• The sequence of degrees of $f_1(x), f_2(x), f_3(x), \cdots, f_N(x)$, read in order, is as lexicographically early as possible.

Write a program that handles the following queries.

• 1 i v: Change $A_i$ to $v$.
• 2 a b: Print $6 \times \int_a^b g(x)dx$.

The first line contains $N$. $(1 \le N \le 200\,000)$

The second line contains $N + 1$ integers $A_0, A_1, A_2, \cdots, A_N$, separated by spaces. $(-100\,000 \le A_i \le 100\,000)$

The third line contains the number of queries $M$. $(1 \le M \le 200\,000)$

Each of the next $M$ lines contains one query. $(0 \le i \le N;$ $-100\,000 \le v \le 100\,000;$ $0 \le a \le b \le N)$

Every input is guaranteed to contain at least one query of type 2.

All input numbers are integers.

For each query of type 2, print the result on its own line, in order. The result of every type 2 query is always an integer, and this can be proven.