26520번 - 다항함수의 적분과 쿼리

길이가 $N + 1$인 수열 $A_0, A_1, A_2, \cdots, A_N$이 주어질 때, $N$개의 다항함수 $f_1(x), f_2(x), f_3(x), \cdots, f_N(x)$와 함수 $g(x)$가 다음 조건에 따라 정해진다.

• $N$ 이하인 모든 음이 아닌 정수 $n$에 대해서 $g(n) = A_n$이다.
• $N$ 이하인 모든 양의 정수 $n$에 대해서 $n - 1 \le x \le n$이면 $g(x) = f_n(x)$이다.
• $g(x)$는 구간 $(0, N)$에서 미분가능하다.
• $f_1(x), f_2(x), f_3(x), \cdots, f_N(x)$의 차수를 나열한 수열이 사전 순으로 가능한 한 앞에 위치하도록 한다.

이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 i v : $A_i$를 $v$로 바꾼다.
• 2 a b : $6 \times \int_a^b g(x)dx$를 출력한다.

첫 번째 줄에 $N$이 주어진다. $(1 \le N \le 200\,000)$

두 번째 줄에 $N + 1$개의 정수 $A_0, A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-100\,000 \le A_i \le 100\,000)$

세 번째 줄에 쿼리의 개수 $M$이 주어진다. $(1 \le M \le 200\,000)$

다음 $M$개의 줄에 쿼리의 정보가 한 줄에 하나씩 주어진다. $(0 \le i \le N;$ $-100\,000 \le v \le 100\,000;$ $0 \le a \le b \le N)$

모든 입력 데이터에서 2번 쿼리가 하나 이상 존재함이 보장된다.

입력되는 모든 수는 정수이다.

각 2번 쿼리의 결과를 한 줄에 하나씩 순서대로 출력한다. 2번 쿼리의 결과가 항상 정수임을 증명할 수 있다.