F. Firefly's Queriestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputFirefly 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$$$.InputThe 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$$$.OutputFor each query, output the answer on a new line.ExampleInput53 31 2 31 93 58 85 54 8 3 2 41 143 77 102 111 251 161 15 73 1 6 10 43 216 172 21 51 149 1512 135 34 9 10 10 120 253 1120 22Output18
8
1
55
20
13
41
105
6
96
62
1
24
71
31
14
44
65
15
NoteFor the first test case, $$$b = [1, 2, 3, 2, 3, 1, 3, 1, 2]$$$.