사탕

Carl은 N개의 사탕 배열을 가지고 있다. 배열의 i번째 원소(1부터 시작)는 Ai이며 i번째 사탕의 단맛 값을 나타낸다. 그는 Q번의 연산을 수행하려고 한다. 연산은 두 가지 종류가 있다.

• 배열에 있는 사탕의 단맛 값을 바꾼다.
• 부분 배열의 단맛 점수를 질의한다.

인덱스 l부터 r까지의 부분 배열에 대한 단맛 점수는 Al × 1 - Al+1 × 2 + Al+2 × 3 - Al+3 × 4 + Al+4 × 5 ... 이다.

더 형식적으로, 단맛 점수는 l부터 r까지의 모든 i에 대해 (-1)i-lAi × (i - l + 1)의 합이다.

예를 들어, 다음의 단맛 점수는:

• [3, 1, 6]은 3 × 1 - 1 × 2 + 6 × 3 = 19
• [40, 30, 20, 10]은 40 × 1 - 30 × 2 + 20 × 3 - 10 × 4 = 0
• [2, 100]은 2 × 1 - 100 × 2 = -198

Carl은 모든 질의의 단맛 점수의 총합을 알고 싶어 한다. 질의 연산이 하나도 없으면 합은 0으로 간주한다. Carl이 합을 구하도록 도와줄 수 있는가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 N과 Q가 있는 한 줄로 시작한다. 두 번째 줄에는 배열을 나타내는 N개의 정수가 있다. i번째 정수는 Ai이다. 다음 Q줄의 j번째 줄은 j번째 연산을 나타낸다. 각 줄은 연산의 종류를 나타내는 문자 하나(U는 갱신, Q는 질의)로 시작한다.

• 갱신 연산이면 두 정수 Xj와 Vj가 이어지며, 배열의 Xj번째 원소를 Vj로 바꾼다는 뜻이다.
• 질의 연산이면 두 정수 Lj와 Rj가 이어지며, Lj번째 원소부터 Rj번째 원소까지(양 끝 포함)의 부분 배열의 단맛 점수를 묻는다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고 y는 모든 질의의 단맛 점수의 총합이다.

• 1 ≤ T ≤ 100.
• 모든 i에 대해 1 ≤ Ai ≤ 100.
• 최대 6개의 테스트 케이스에서 1 ≤ N ≤ 2 × 105이고 1 ≤ Q ≤ 105이다.
• 나머지 테스트 케이스에서는 1 ≤ N ≤ 300이고 1 ≤ Q ≤ 300이다.
• j번째 연산이 갱신 연산이면 1 ≤ Xj ≤ N이고 1 ≤ Vj ≤ 100.
• j번째 연산이 질의 연산이면 1 ≤ Lj ≤ Rj ≤ N.

예제 케이스 #1에서:

• 첫 번째 질의는 [3, 9, 8]의 단맛 점수를 묻고, 이는 3 × 1 - 9 × 2 + 8 × 3 = 9이다.
• 두 번째 질의는 [2]의 단맛 점수를 묻고, 이는 2 × 1 = 2이다.
• 세 번째 질의는 [1, 10]의 단맛 점수를 묻고, 이는 1 × 1 - 10 × 2 = -19이다.

따라서 최종 출력은 9 + 2 - 19 = -8이어야 한다.

예제 케이스 #2에서:

• 첫 번째이자 유일한 질의는 [7, 5]의 단맛 점수를 묻고, 이는 7 × 1 - 5 × 2 = -3이다.

따라서 최종 출력은 -3이어야 한다.