SPOJ in Gyumri

   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 input starts with an integer t in the first line that denotes the number of test cases in this problem (1 ≤ t ≤ 5).

   Each test case starts with a blank line, followed by a line that contains 2 integers: n and q (1 ≤ n, q ≤ 100,000).

   Then, the next line contains n non-negative integers up to 1,000,000,000. Then q lines follow.

   Each line contains two integers, i and j (0 ≤ i, j < 10,000).

Output

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

Examples