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