Range Sum Queries Using Prefix Sums

You are given an array of integers scores and a list of range queries. Each query is represented by two integers L and R (0-indexed), and your task is to compute the sum of elements in the array from index L to index R (inclusive).

To solve this problem efficiently, you should use the prefix sums technique. Define the prefix sum array \(S\) as follows:

[ S[i] = \sum_{j=0}^{i-1} a[j],\quad \text{for } 1 \leq i \leq n, \quad \text{with } S[0] = 0. ]

Then, the sum of the elements between indices \(L\) and \(R\) can be computed by:

[ \text{sum} = S[R+1] - S[L]. ]

Implement a program that reads the input from standard input (stdin) and prints the answer for each query to the standard output (stdout).

inputFormat

The input consists of multiple test cases. For each test case, the input format is as follows:

• The first line contains an integer T representing the number of test cases. (For each separate run of your program, assume that the first number in the input is the number of test cases in that run.)
• For each test case:
• The first line contains two integers N and Q where N is the number of elements in the scores array and Q is the number of queries.
• The second line contains N space-separated integers representing the scores.
• Then follow Q lines, each containing two integers L and R (0-indexed) representing a query.

Note: In the test cases provided below, each test input contains a single test case (i.e. the first number is 1), but your solution should support multiple test cases.

outputFormat

For each query, output the sum of the elements in the specified range on a new line. The outputs for different queries (and different test cases) should be printed sequentially in the order in which the queries are given.

## sample

1
1 1
5
0 0

5

</p>