Range Sum Query#6959
Sign in

Range Sum Query

1 second
128 megabytes
Very easy

The list contains integers. Find the sum of the numbers on the segment between indices and inclusive, i.e.,

RSQ(i, j) = L_i + L_{i + 1} + L_{i + 2} + ... + L_j

Input

The first line contains the number of test cases t~(1 \le t \le 5). Each test starts with an empty line, followed by a line with two integers and q~(1 \le n, q \le 10^5). The next line contains non-negative integers, each no greater than 10^9. Then, lines follow, each containing two integers and j~(0 \le i, j < n).

Output

For each query, output the value of RSQ(i, j) in a separate line. Separate the answers for different test cases with an empty line.

Examples

Example 1

Loading
Loading