Given a list L containing n integers, find the Range Sum Query (RSQ) between index i and j, inclusive, i.e.
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≤105). Then, the next line contains n non-negative integers up to 109. Then q lines follow. Each line contains two integers i and j (0≤i,j<10000).
For each query, print a line containing the value of RSQ(i,j). Separate two test cases with a blank line.