세 수의 곱

한 선생님이 학생들의 계산 능력을 확인하려고 한다. 삼중곱을 서로 다른 세 위치에 있는 세 수의 곱으로 정의하자.

선생님은 칠판에 자연수 $n$개를 한 줄로 적는다. 이후 선생님은 어떤 수를 다른 자연수로 바꾸거나, 칠판의 특정 구간에 있는 수들로 만들 수 있는 모든 삼중곱의 합을 물어본다. 서로 다르다는 것은 값이 아니라 위치를 기준으로 한다. 즉 고른 두 수의 값이 같아도 위치가 다르면 서로 다른 선택으로 본다.

모든 질의에 답하여라.

첫 줄에 테스트 케이스의 수 $Z$가 주어진다(여기서는 $Z = 1$).

각 테스트 케이스는 다음과 같이 주어진다.

• 자연수 $n$ ($1 \le n \le 200000$)이 한 줄에 주어진다.
• 다음 줄에 칠판의 처음 수 $n$개가 공백으로 구분되어 주어진다.
• 다음 줄에 연산의 수 $q$ ($1 \le q \le 200000$)가 주어진다.
• 그다음 $q$개의 줄에 각 연산이 다음 형식으로 주어진다.
  • Z a b ($1 \le a \le n$, $b > 0$): 위치 $a$의 수를 자연수 $b$로 바꾼다.
  • Q a b ($1 \le a \le b \le n$): 구간 $[a, b]$에 있는 수들로 만들 수 있는 모든 삼중곱의 합을 구한다.

어느 순간에도 칠판에 있는 모든 수의 합은 백만($10^6$)을 넘지 않는다.

각 Q 연산마다 한 줄에 자연수 하나를 출력한다. 질의한 구간에서 서로 다른 세 위치를 골라 만들 수 있는 모든 삼중곱의 합이다.

칠판이 $[1, 3, 2, 2]$일 때 구간 $[1, 4]$에 대한 첫 질의의 답은 $1\cdot3\cdot2 + 1\cdot3\cdot2 + 1\cdot2\cdot2 + 3\cdot2\cdot2 = 28$ 이다. 두 번째 질의의 구간에는 수가 두 개뿐이라 삼중곱을 만들 수 없으므로 답은 $0$이다. 위치 $1$의 수를 $2$로 바꾸면 칠판은 $[2, 3, 2, 2]$가 되고, 구간 $[1, 3]$에 대한 세 번째 질의의 답은 $2\cdot3\cdot2 = 12$이다.