F. Firefly's Queries
bitmasks; data structures; flows; math
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]\).