该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

读写要求

本题采用文件读写，请在提交代码时使用正确的文件名，否则会导致 RE。

输入文件：firefly.in

输出文件：firefly.out

题目描述

Firefly 有一个长度为 $n$ 的数组 $a$。设 $c_i$ 表示 $a$ 的第 $i$ 个循环移位（$1\le i\le n$），即 $c_i=[a_i,a_{i+1},\dots,a_n,a_1,a_2,\dots,a_{i-1}]$。

她创建一个新的数组 $b$，使得 $b=c_1+c_2+\dots+c_n$，其中 $+$ 表示数组的拼接。

然后她会提出 $q$ 个询问。对于每个询问，输出 $b$ 中从第 $l$ 个元素到第 $r$ 个元素（含两端）的子数组的元素之和。

输入格式

第一行一个整数 $t$，表示测试用例组数。

每组测试数据：

第一行两个整数 $n,q$，表示数组长度和询问数量。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $q$ 行，每行两个整数 $l,r$（$1\le l\le r\le n^2$），表示询问区间。

注意可能需要使用 64 位整数。

保证所有测试用例的 $n$ 之和与 $q$ 之和均不超过 $2\times 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

数据范围

• $1\le n,q\le 2\times 10^5$，$\sum n\le 2\times 10^5$，$\sum q\le 2\times 10^5$
• $1\le a_i\le 10^6$