给定一个长度为n 的数组 a。让c_i表示i 的第 i' 次循环移位 ^{\text{∗}} 的结果。这个数组一共循环n次，以a数列[1,2,3]为例，循环过后就形成了[1,2,3,2,3,1,3,1,2]这么一个b数列。

然后，提出 q 个查询。对于每个查询，输出从第l 个元素到第 r 个元素（包括两端）的子数组 b 中所有元素的和。

数组 a 的第 x 次(1 \leq x \leq n) 循环移位是 a_x, a_{x+1} \ldots a_n, a_1, a_2 \dots a_{x - 1}。注意，第1 次移位是初始的 a。

第一行包含 t (1 \leq t \leq 100) — 测试用例的数量。

每个测试用例的第一行包含两个整数 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。

对于每个查询，在新的一行中输出答案。

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

性质A：其中10%的数据保证，n=1,q\leq   100,a_i \leq 10^9,t (1 \leq t \leq 10)

性质B：另有20%的数据保证，n,q\leq 1000,a_i \leq 10^9,t (1 \leq t \leq 10)；

性质C：另有20%的数据保证，n,q\leq 2 \times 10^5,a_i=0，t (1 \leq t \leq 10)。

性质D：另有50%的数据保证，，n,q\leq 2 \times 10^5,a_i \leq 10^9，t (1 \leq t \leq 5)。