题目描述

Alice 向她的朋友 Bob 展示了一个包含 $N$ 个正整数的数组，下标从 $1$ 到 $N$。她向 Bob 提出了许多形如“这两个下标之间的数之和是多少？”的查询，但 Bob 太容易地解决了问题。

Alice 取出了她的数组，并找出了它的所有 $N \times (N + 1) / 2$ 个非空子数组。她求出了每个子数组的和，然后将这些值按非递减顺序排序，从而创建了一个新数组，下标从 $1$ 到 $N \times (N + 1) / 2$。例如，对于初始数组 $[2, 3, 2]$，Alice 将生成子数组 $[2], [3], [2], [2, 3], [3, 2]$ 和 $[2, 3, 2]$（注意，例如 $[2, 2]$ 不是 一个子数组）。然后她取出这些和——$2, 3, 2, 5, 5, 7$——并对它们排序，得到新数组 $[2, 2, 3, 5, 5, 7]$。

Alice 已将初始数组以及 $Q$ 个形如“在新数组中从下标 $L_i$ 到 $R_i$（含）的数之和是多少？”的查询交给了 Bob。现在 Bob 陷入困境了！你能帮他脱困吗？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以一行包含两个由空格分隔的整数 $N$ 和 $Q$ 开始，分别表示初始数组的元素个数和 Alice 的查询个数。然后，有一行包含 $N$ 个由空格分隔的整数，表示 Alice 初始数组的元素。最后，还有 $Q$ 行，每行包含两个由空格分隔的整数：$L_i$ 和 $R_i$，即第 $i$ 个查询的闭区间下标边界。

输出格式

对于每个测试用例，输出一行 Case #x:，其中 $x$ 是测试用例编号（从 $1$ 开始）。然后再输出 $Q$ 行，每行一个整数，表示查询的答案（按询问顺序）。

1
5 5
5 4 3 2 1
1 1
1 10
1 15
3 8
4 11

Case #1:
1
45
105
26
48

提示

在样例用例 #1 中，Alice 的新数组将是：$[1, 2, 3, 3, 4, 5, 5, 6, 7, 9, 9, 10, 12, 14, 15]$。

限制

• $1 \le T \le 10$。
• $1 \le Q \le 20$。
• $1 \le \text{初始数组的每个元素} \le 100$。
• $1 \le L_i \le R_i \le N \times (N+1) / 2$。

小数据集（测试集 1 - 可见）

• $1 \le N \le 10^3$。

大数据集（测试集 2 - 隐藏）

• $1 \le N \le 200000$。

翻译由 DeepSeek V4 Pro 完成