Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0116 - RANGE SUM QUERY

   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 (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

stdin

stdout

1

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

Ավելացրեց.Հրանտ Հովհաննիսյան (ԳՏՏԿ)
Ամսաթիվ.2014-02-01
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Thailand Southern 2013.G

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.