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].

입력 형식

The input starts with an integer t in the first line that denotes the number of test cases in this problem (1 ≤ t ≤ 5).</p>

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

출력 형식

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

예제 입력

2

5 2
1 2 3 4 5
4 4
1 3

10 5
10 9 7 20 14 23 14 27 38 77
8 9
7 9
6 9
5 9
4 9

예제 출력

5
9

115
142
156
179
193