Prefix Sum Queries

You are given an array of integers. Your task is to precompute the prefix sums of the array and answer multiple range sum queries efficiently. For each query, given two indices \(l\) and \(r\) (1-indexed), you need to determine the sum of the subarray from index \(l\) to \(r\).

The prefix sum array \(P\) is defined as \(P[i] = a_1 + a_2 + \dots + a_i\) for \(1 \leq i \leq n\) with \(P[0] = 0\). Using this, the sum for a range \([l, r]\) can be computed as \(P[r] - P[l-1]\).

inputFormat

The first line contains an integer (T), the number of test cases. For each test case, the first line contains two integers (n) and (q), where (n) is the number of elements and (q) is the number of queries. The next line contains (n) space-separated integers representing the array. Each of the following (q) lines contains two integers (l) and (r), indicating a query for the sum of the subarray from index (l) to (r) (1-indexed).

outputFormat

For each query, print a single integer – the sum of the subarray from index (l) to (r). Each answer should be printed on a new line.## sample

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

6
14
15