题目描述

Carl 有 $N$ 颗糖果组成的数组。数组的第 $i$ 个元素（下标从 $1$ 开始）为 $A_i$，表示第 $i$ 颗糖果的甜度值。他想执行一系列 $Q$ 个操作。操作有两种类型：

• 更新数组中某颗糖果的甜度值。
• 查询某个子数组的甜度分数。

从下标 $l$ 到 $r$ 的子数组的甜度分数定义为： $A_l \times 1 - A_{l+1} \times 2 + A_{l+2} \times 3 - A_{l+3} \times 4 + A_{l+4} \times 5 \dots$

形式化地，甜度分数为 $\sum_{i=l}^{r} (-1)^{i-l} A_i \times (i - l + 1)$。

例如：

• $[3, 1, 6]$ 的甜度分数为 $3 \times 1 - 1 \times 2 + 6 \times 3 = 19$。
• $[40, 30, 20, 10]$ 的甜度分数为 $40 \times 1 - 30 \times 2 + 20 \times 3 - 10 \times 4 = 0$。
• $[2, 100]$ 的甜度分数为 $2 \times 1 - 100 \times 2 = -198$。

Carl 想求出所有查询操作的甜度分数之和。如果没有查询操作，则和为 $0$。你能帮助 Carl 求出这个和吗？

输入格式

输入的第一行给出测试用例的数量 $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$ 是所有查询操作的甜度分数之和。

2
5 4
1 3 9 8 2
Q 2 4
Q 5 5
U 2 10
Q 1 2
3 3
4 5 5
U 1 2
U 1 7
Q 1 2

Case #1: -8
Case #2: -3

提示

在样例 #1 中：

• 第一个查询询问子数组 $[3, 9, 8]$ 的甜度分数，计算为 $3 \times 1 - 9 \times 2 + 8 \times 3 = 9$。
• 第二个查询询问子数组 $[2]$ 的甜度分数，计算为 $2 \times 1 = 2$。
• 第三个查询询问子数组 $[1, 10]$ 的甜度分数，计算为 $1 \times 1 - 10 \times 2 = -19$。

因此最终输出为 $9 + 2 - 19 = -8$。

在样例 #2 中：

• 第一个（也是唯一一个）查询询问子数组 $[7, 5]$ 的甜度分数，计算为 $7 \times 1 - 5 \times 2 = -3$。

因此最终输出为 $-3$。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$1 \le A_i \le 100$。

最多 $6$ 个测试用例满足 $1 \le N \le 2 \times 10^5$ 且 $1 \le Q \le 10^5$。

其余测试用例满足 $1 \le N \le 300$ 且 $1 \le Q \le 300$。

如果第 $j$ 个操作为更新操作，则 $1 \le X_j \le N$ 且 $1 \le V_j \le 100$。

如果第 $j$ 个操作为查询操作，则 $1 \le L_j \le R_j \le N$。

测试集 1

最多有 $5$ 个更新操作。

测试集 2

无特殊限制。

翻译由 DeepSeek V4 Pro 完成