Range Sum Query

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

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 $n$ and $q(1\le n,q\le 10^5)$. The next line contains $n$ non-negative integers, each no greater than $10^9$. Then, $q$ lines follow, each containing two integers $i$ 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