Sums of Sums (Large)

Alice gave her friend Bob an array of $N$ positive integers, indexed from $1$ to $N$. She asked him many queries of the form "what is the sum of the numbers between these two indexes?", and Bob answered them without any trouble.

So Alice took her array and found all $N(N+1)/2$ non-empty subarrays of it. She computed the sum of each subarray, then sorted those sums in nondecreasing order into a new array, indexed from $1$ to $N(N+1)/2$. For the initial array $[2, 3, 2]$ the subarrays are $[2]$, $[3]$, $[2]$, $[2, 3]$, $[3, 2]$, $[2, 3, 2]$. Note that $[2, 2]$ is not a subarray. Their sums are $2$, $3$, $2$, $5$, $5$, $7$, and sorting them gives the new array $[2, 2, 3, 5, 5, 7]$.

Alice hands Bob the initial array together with $Q$ queries of the form "what is the sum of the numbers from index $L_i$ to index $R_i$, inclusive, in the new array?" Now Bob is stuck. Help him out.

The first line contains the number of test cases, $T$. $T$ test cases follow.

Each test case begins with one line holding two space separated integers $N$ and $Q$, the number of elements of the initial array and the number of queries. The next line holds $N$ space separated integers, the elements of the initial array. Then come $Q$ lines with two space separated integers each, $L_i$ and $R_i$, the inclusive index bounds of the $i$-th query.

Limits

• $1 \le T \le 10$
• $1 \le Q \le 20$
• every element of the initial array is between $1$ and $100$
• $1 \le L_i \le R_i \le N(N+1)/2$
• $1 \le N \le 200000$

For each test case, print one line with Case #x:, where $x$ is the test case number starting from $1$. Then print $Q$ lines, each with one integer, the answers to the queries in the order they were asked.

For the array $[5, 4, 3, 2, 1]$, the new array is $[1, 2, 3, 3, 4, 5, 5, 6, 7, 9, 9, 10, 12, 14, 15]$.