Problems
Range Sum Query
Range Sum Query
Given a list $L$ containing $n$ integers, find the Range Sum Query (RSQ) between index $i$ and $j$, inclusive, i.e.
$$
RSQ(i, j) = L_i + L_{i + 1} + L_{i + 2} + ... + L_j
$$
\InputFile
The first line contains the number of test cases $t~(1 \le t \le 5)$. Each test case starts with a blank line, followed by a line that contains two integers $n$ and $q~(1 \le n, q \le 10^5)$. Then, the next line contains $n$ non-negative integers up to $10^9$. Then $q$ lines follow. Each line contains two integers $i$ and $j~(0 \le i, j < 10000)$.
\OutputFile
For each query, print a line containing the value of $RSQ(i, j)$. Separate two test cases with a blank line.
Input example #1
2 5 2 1 2 3 4 5 4 4 1 3 10 5 10 9 7 20 14 23 14 27 38 77 8 9 7 9 6 9 5 9 4 9
Output example #1
5 9 115 142 156 179 193