Subarray Sum Queries

You are given an array of integers and several queries. Each query asks you to calculate the sum of elements within a subarray defined by its starting index L and ending index R (1-indexed). For each query, output the sum of the subarray.

Task: For each test case, compute the prefix sums and use them to answer the queries quickly.

Note: The indices provided in the queries follow 1-indexing.

inputFormat

The input is given from stdin in the following format:

T
N Q
A[1] A[2] ... A[N]
L1 R1
L2 R2
... (total Q lines for queries)
... (Repeat the above block for each of the T test cases)

Where:

• T: Number of test cases.
• N: Size of the array for each test case.
• Q: Number of queries for that test case.
• A[i]: The i-th element of the array.
• L and R: The starting and ending indices (1-indexed) of the subarray.

outputFormat

For each query in each test case, print the sum of the subarray on a new line to stdout.

## sample

1
5 3
1 2 3 4 5
1 3
2 5
1 5

6
14
15

</p>