Total Car Value in Price Range

You are given a sorted list of car prices and a series of queries. Each query specifies a price range [L, R] (inclusive), and your task is to calculate the sum of the car prices that fall within that range. To achieve an efficient solution, you are encouraged to use binary search combined with prefix sums.

Mathematically, if the sorted list of car prices is \(a_1, a_2, \dots, a_N\) and its prefix sum array is defined as \(P(i) = \sum_{j=1}^{i} a_j\) with \(P(0)=0\), then for each query with bounds \(L\) and \(R\), you need to find the smallest index \(i\) such that \(a_i \ge L\) and the largest index \(j\) such that \(a_j \le R\). The answer for that query is \(P(j) - P(i-1)\) if such indices exist (and 0 otherwise).

Note: It is guaranteed that the list of car prices is given in non-decreasing order.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N Q
price1 price2 ... priceN
L1 R1
L2 R2
... 
LQ RQ
... (The above test case repeats T times)

</p>

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers N (the number of car prices) and Q (the number of queries).
• The next line contains N integers representing the sorted list of car prices.
• Each of the following Q lines contains two integers L and R defining the price range (inclusive) for a query.

outputFormat

For each test case, output one line containing Q integers. Each integer is the total sum of car prices that fall within the corresponding query's price range. The results for a test case should be space-separated and printed on a new line.

## sample

1
5 3
10000 20000 30000 40000 50000
15000 35000
5000 25000
20000 60000

50000 30000 140000