← 返回题目列表

Codeforces · 2009/F

F. 萤火虫的查询

中文机器翻译题面 查看原题

Firefly 被赋予一个长度为 $$$n$$$ 的数组 $$$a$$$。设$$$c_i$$$表示$$$a$$$的第$$$i$$$循环移位$$$^{\text{*}}$$$。她创建了一个新数组 $$$b$$$,使得 $$$b = c_1 + c_2 + \dots + c_n$$$,其中 $$$+$$$ 表示串联 $$$^{\text{†}}$$$。

然后,她会问你 $$$q$$$ 问题。对于每个查询,输出 $$$b$$$ 子数组中从第 $$$l$$$ 个元素开始到第 $$$r$$$ 个元素(包括两端)的所有元素的总和。

输入

第一行包含 $$$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$$$) — 查询的左边界和右边界。

请注意,大输入可能需要使用 64 位整数。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$,$$$q$$$之和不超过$$$2 \cdot 10^5$$$。

输出

对于每个查询,在新行中输出答案。

示例

输入 #1

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

输出 #1

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]$$$。