사탕

Carl에게 N개의 사탕으로 이루어진 배열이 있다. 배열의 i번째 원소는 (1부터 인덱스가 매겨진다) $A_{i}$이며, i번째 사탕의 단맛 값을 나타낸다. 그는 Q개의 연산을 차례로 수행하려고 한다. 연산에는 두 가지 유형이 있다:

• 배열에 있는 사탕 하나의 단맛 값을 갱신한다.

• 부분 배열의 단맛 점수를 질의한다.

인덱스 l부터 r까지인 부분 배열의 단맛 점수는 다음과 같다: $A_{l}$ × 1 - $A_{l+1}$ × 2 + $A_{l+2}$ × 3 - $A_{l+3}$ × 4 + $A_{l+4}$ × 5 ...

더 형식적으로, 단맛 점수는 l부터 r까지의 모든 i에 대해 (-1)^{i - l}$A_{i}$ × (i - l + 1)의 합이다. 이때 l과 r도 범위에 포함된다.

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

• $[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이 이 합을 구하도록 도와줄 수 있는가?

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 모든 i에 대해 1 ≤ $A_{i}$ ≤ 100. 최대 6개의 테스트 케이스에서는 1 ≤ N ≤ 2 × $10^{5}$이고, 1 ≤ Q ≤ $10^{5}$이다. 나머지 케이스에서는 1 ≤ N ≤ 300이고, 1 ≤ Q ≤ 300이다. j번째 연산이 갱신 연산이라면, 1 ≤ $X_{j}$ ≤ N이고 1 ≤ $V_{j}$ ≤ 100이다. j번째 연산이 질의 연산이라면, 1 ≤ $L_{j}$ ≤ $R_{j}$ ≤ N이다.

Test Set 1

갱신 연산은 최대 5개이다.

Test Set 2

특별한 제약 조건은 없다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 N과 Q가 포함된 한 줄로 시작한다. 두 번째 줄에는 배열을 설명하는 N개의 정수가 주어진다. i번째 정수는 $A_{i}$이다. 이어지는 Q개 줄 중 j번째 줄은 j번째 연산을 설명한다. 각 줄은 연산 유형을 설명하는 하나의 문자로 시작한다(갱신은 U, 질의는 Q).

• 갱신 연산에서는 두 정수 $X_{j}$와 $V_{j}$가 이어서 주어지며, 이는 배열의 $X_{j}$번째 원소가 $V_{j}$로 변경됨을 나타낸다.

• 질의 연산에서는 두 정수 $L_{j}$와 $R_{j}$가 이어서 주어지며, $L_{j}$번째 원소부터 $R_{j}$번째 원소까지의 부분 배열에 대한 단맛 점수를 질의한다(양 끝 원소도 포함한다).

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

예제 케이스 #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이어야 한다.