题目描述

Firefly 有一个长度为 $n$ 的数组 $a$。令 $c_i$ 表示 $a$ 的第 $i$ 次循环移位$^{\text{∗}}$。她创建了一个新数组 $b$，使得 $b = c_1 + c_2 + \dots + c_n$，其中 $+$ 表示拼接$^{\text{†}}$。

接着，她会给你 $q$ 个询问。对于每个询问，输出 $b$ 的从第 $l$ 个元素到第 $r$ 个元素（包括两端）组成的子数组的所有元素之和。

$^{\text{∗}}$ 数组 $a$ 的第 $x$ 次循环移位（$1 \leq x \leq n$）为 $a_x, a_{x+1}, \ldots, a_n, a_1, a_2, \ldots, a_{x-1}$。注意，第 $1$ 次移位就是原始的 $a$。

$^{\text{†}}$ 两个长度为 $n$ 的数组 $p$ 和 $q$ 的拼接（即 $p + q$）为 $p_1, p_2, ..., p_n, q_1, q_2, ..., q_n$。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 2 \cdot 10^5$），分别表示数组的长度和询问的数量。

接下来一行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^6$）。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n^2$），表示询问的区间左右端点。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$q$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个询问，输出一个答案，每行一个。

样例

5
3 3
1 2 3
1 9
3 5
8 8
5 5
4 8 3 2 4
1 14
3 7
7 10
2 11
1 25
1 1
6
1 1
5 7
3 1 6 10 4
3 21
6 17
2 2
1 5
1 14
9 15
12 13
5 3
4 9 10 10 1
20 25
3 11
20 22

18
8
1
55
20
13
41
105
6
96
62
1
24
71
31
14
44
65
15

样例说明

对于第一个测试用例，$b = [1, 2, 3, 2, 3, 1, 3, 1, 2]$。

由 ChatGPT 4.1 翻译

来源

Codeforces 2009F，英文题名 Firefly's Queries。