Range Sum Query

Given a list $L$ containing $n$ integers, find the Range Sum Query (RSQ) between index $i$ and $j$, inclusive, i.e.

Input

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)$.

Output

For each query, print a line containing the value of $RSQ(i,j)$. Separate two test cases with a blank line.

Examples