给定一个长度为$n$ 的数组 $a$。让$c_i$表示$i$ 的第 $i'$ 次循环移位 $^{\text{∗}}$ 的结果。她创建了一个新数组 $b$，使得 $b = c_1 + c_2 + \dots + c_n$，其中 $+$代表连接$^{\\text{†}}$。

然后，提出 $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$。

两个长度为 $n$的数组 $p$和 $q$的连接（换句话说，$p+q$）是$p_1, p_2, ..., p_n, q_1, q_2, ..., q_n$。

第一行包含 $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]$。

40%的数据，$n,q\leq 1000$；

100%的数据，$n,q\leq 2 \times 10^5$，$t (1 \leq t \leq 100)$。