Firefly is given an array (a) of length (n). Let (c_i) denote the (i)'th cyclic shift(^{\text{∗}}) of (a). She creates a new array (b) such that (b = c_1 + c_2 + \dots + c_n) where (+) represents concatenation(^{\text{†}}). Then, she asks you (q) queries. For each query, output the sum of all elements in the subarray of (b) that starts from the (l)-th element and ends at the (r)-th element, inclusive of both ends. (^{\text{∗}})The (x)-th ((1 \leq x \leq n)) cyclic shift of the array (a) is (a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1}). Note that the (1)-st shift is the initial (a). (^{\text{†}})The concatenation of two arrays (p) and (q) of length (n) (in other words, (p + q)) is (p_1, p_2, ..., p_n, q_1, q_2, ..., q_n). The first line contains (t) ((1 \leq t \leq 10^4)) — the number of test cases. The first line of each test case contains two integers (n) and (q) ((1 \leq n, q \leq 2 \cdot 10^5)) — the length of the array and the number of queries. The following line contains (n) integers (a_1, a_2, ..., a_n) ((1 \leq a_i \leq 10^6)). The following (q) lines contain two integers (l) and (r) ((1 \leq l \leq r \leq n^2)) — the left and right bounds of the query. Note that the large inputs may require the use of 64-bit integers. It is guaranteed that the sum of (n) does not exceed (2 \cdot 10^5) and the sum of (q) does not exceed (2 \cdot 10^5). For each query, output the answer on a new line. For the first test case, (b = 1, 2, 3, 2, 3, 1, 3, 1, 2).