给定一个长度为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)。