Nexus 4.O is going to be organized by ASME, GLA University. Shubhanshu, Head of Finance Team is working for it. He has $N$ number of bills of different values as $a$$1$,$ a$$2$, $a$$3$…$a$$n$.
He is interested in a game in which one has to do the addition of the bills. But due to privacy concerns, he cannot share the details with others. 
He can only trust his best friend Avani with such a confidential thing. So, he asked her to play this game.
Rules of the game :
- Avani needs to answer $Q$ queries.
- Every $Q$$i$ query has 2 values $X$$i$ and $Y$$i$.
- Avani needs to find the sum of the values between $X$$i$ and $Y$$i$ (inclusive).
So, you need to help Avani in answering the $Q$ queries

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line of each test case contains the value $N$ and $Q$.
- The second line of each test case contains the $N$ space-separated values as $a$$1$,$ a$$2$, $a$$3$…$a$$n$.
- The next line of each test case containing $Q$ query with $X$$i$ and $Y$$i$.

-----Output:-----
For each test case, Print the total amount between $X$$i$ and $Y$$i$ for $Q$ number of queries.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^5$
- $1 \leq Q \leq 10^5$
- $1 \leq a$$i$$ \leq 10^9$

-----Subtasks (25 points) :-----
- $1 \leq N \leq 10^2$.
- $1 \leq Q \leq 10^2$.
- $1 \leq a$$i$$ \leq 10^5$.

-----Subtasks (25 points) :-----
- $1 \leq N \leq 10^3$.
- $1 \leq Q \leq 10^3$.
- $1 \leq a$$i$$ \leq 10^5$.

-----Subtasks (50 points) :-----
- $Original  Constraints$.

-----Sample Input:-----
1
8 3
1 2 3 4 5 6 7 8
2 3
1 6
5 8

-----Sample Output:-----
5
21
26

-----EXPLANATION:-----
$Q$$1$ : (2,3) 2+3=5
$Q$$2$ : (1,6) 1+2+3+4+5+6=21
$Q$$3$ : (5,8) 5+6+7+8=26

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "\nt=int(input())\nfor i in range(t):\n l=list(map(int,input().split(' ')))\n a=l[0]\n b=l[1]\n \n l1=list(map(int,input().split(' ')))\n for i in range(b):\n  l2=list(map(int,input().split(' ')))\n  a1=l2[0]\n  b1=l2[1]\n  su=0\n  for j in range(a1-1,b1):\n   su=(su+l1[j])%1000000000\n  print(su) "
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13291