# Range Sum Query

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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}$

## Input

The first line contains the number of test cases $t(1≤t≤5)$. Each test case starts with a blank line, followed by a line that contains two integers $n$ and $q(1≤n,q≤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≤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

Input #1

Answer #1

Submissions 2K

Acceptance rate 35%