CF2009F Firefly's Queries

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] $ .