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

Difficulty: interview

Starter code:

Solutions:

t=int(input())
for i in range(t):
 l=list(map(int,input().split(' ')))
 a=l[0]
 b=l[1]
 
 l1=list(map(int,input().split(' ')))
 for i in range(b):
  l2=list(map(int,input().split(' ')))
  a1=l2[0]
  b1=l2[1]
  su=0
  for j in range(a1-1,b1):
   su=(su+l1[j])%1000000000
  print(su) 


t=int(input())
for i in range(t):
 l=list(map(int,input().split(' ')))
 a=l[0]
 b=l[1]
 
 l1=list(map(int,input().split(' ')))
 for i in range(b):
  l2=list(map(int,input().split(' ')))
  a1=l2[0]
  b1=l2[1]
  su=0
  for j in range(a1-1,b1):
   su=(su+l1[j])%1000000000
  print(su) 

tc=int(input())
for i in range(0,tc):
 n,q=list(map(int,input().split()))
 l=[]
 l=list(map(int,input().split()))
 for j in range(0,q):
  x,y=list(map(int,input().split()))
  sum=0
  for k in range(x,y+1):
   sum=sum+l[k-1]
  print(sum) 


import math
t=int(input())
for ii in range(t):
 n,q=[int(x) for x in input().split()]
 arr=[int(x) for x in input().split()]
 pre=[]
 s=0
 for i in arr:
  s+=i
  pre.append(s)
 for i in range(q):
  l,r=[int(x) for x in input().split()]
  l-=1
  r-=1
  if(l==0):
   print(pre[r])
  else:
   print(pre[r]-pre[l-1])


# cook your dish here
for _ in range(int(input())):
 N,Q=input().split()
 L=list(map(int,input().split()))
 for i in range(int(Q)):
  X,Y=map(int,input().split())
  s=0
  for i in range(X-1,Y):
   s+=L[i]
  print(s)

# cook your dish here
for _ in range(int(input())):
 N,Q=list(map(int,input().split()))
 L=list(map(int,input().split()))
 for i in range(Q):
  X,Y=list(map(int,input().split()))
  print(sum(L[X-1:Y]))



t=int(input())
for i in range(t):
 l=list(map(int,input().split(' ')))
 a=l[0]
 b=l[1]
 
 l1=list(map(int,input().split(' ')))
 for i in range(b):
  l2=list(map(int,input().split(' ')))
  a1=l2[0]
  b1=l2[1]
  su=0
  for j in range(a1-1,b1):
   su=(su+l1[j])%1000000000
  print(su) 

# cook your dish here
n=int(input())
for i in range(n):
 a,b=input().split()
 b=int(b)
 l=list(map(int,input().split()))
 x=[0]
 for j in l: 
  x.append(x[-1]+j)
 for j in range(b):
  e,f=input().split()
  print(x[int(f)]-x[int(e)-1])



for case in range(int(input())):
 n, q = list(map(int, input().split()))
 arr = list(map(int, input().split()))

 dic = {0:0}
 for i in range(1,n+1):
  dic[i] = dic[i-1] + arr[i-1]
 
 for que in range(q):
  xi, yi = list(map(int, input().split()))

  print(dic[yi] - dic[xi-1])


T = int(input())
for i in range(T):
 a = input().split(" ")
 N = int(a[0])
 Q = int(a[1])
 if(N>=1 and N<=100000 and Q>=1 and Q<=100000):
  b = input().split(" ")
  l = list(map(int,b))
  l1 = []
  for k in range(Q):
   q = input().split(" ")
   l1.extend(q)
     
  l2 = list(map(int,l1))
  m = 0
  while(m<len(l2)-1):
   s = 0
   c = l2[m]
   d = l2[m+1]
   for t in range(c-1,d):
    s = s + l[t] 
   print(s)
   m = m+2


T=int(input())
while(T!=0):
 n,q=[int(x) for x in input().split(' ')]
 N=[int(x) for x in input().split(' ')]
 while(q!=0):
  s=0
  x,y=[int(x) for x in input().split(' ')]
  for i in range(x-1,y):
   s=s+N[i]
  print(s)
  q-=1
 T-=1

# cook your dish here
for u in range(int(input())):
 n,k=map(int,input().split())
 l=list(map(int,input().split()))
 for q in range(k):
  x,y=map(int,input().split())
  print(sum(l[x-1:y]))

# cook your dish here
for u in range(int(input())):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 for q in range(k):
  x,y=list(map(int,input().split()))
  s=0
  for i in range(x-1,y):
   s=s+l[i]

  print(s)


# cook your dish here
t=int(input())
while t>0:
 t-=1
 n,tt=map(int,input().split())
 #print(tt)
 l=list(map(int,input().split()))
 while tt>0:
  a,b=map(int,input().split())
  print(sum(l[a-1:b]))
  tt -= 1

for _ in range(int(input())):
 n, q = map(int, input().split())
 a = list(map(int, input().split()))

 p = [0]

 for i in a:
  p.append(p[-1] + i)

 for _ in range(q):
  x, y = map(int, input().split())

  print(p[y] - p[x - 1])

# cook your dish here
t=int(input())
for i in range(t):
 l=list(map(int,input().split(' ')))
 a=l[0]
 b=l[1]
 
 l1=list(map(int,input().split(' ')))
 for i in range(b):
  l2=list(map(int,input().split(' ')))
  a1=l2[0]
  b1=l2[1]
  print(sum(l1[a1-1:b1]))


# cook your dish here
n=int(input())
for i in range(n):
 a,b=input().split()
 b=int(b)
 l=list(map(int,input().split()))
 for j in range(b):
  x,y=input().split()
  x=int(x)-1
  y=int(y)
  print(sum(l[x:y]))


# cook your dish here
noofcases=int(input())
for _ in range(noofcases):
 numqui=input().split()
 data=list(map(int,input().split()))
 for _ in range(int(numqui[1])):
  sum=0
  startstop=list(map(int,input().split()))
  for j in range(startstop[0]-1,startstop[1]):
   sum+=data[j]
  print(sum)

# cook your dish here
T = int(input())
for i in range(T):
 N,Q = map(int,input().split())
 lis = list(map(int,input().split()))
 cumSum = [0]
 for j in lis:
  cumSum.append(cumSum[-1]+j)
 for j in range(Q):
  x,y = map(int,input().split())
  print(cumSum[y]-cumSum[x-1])

for _ in range(int(input())):
 n,q=map(int,input().split())
 arr=list(map(int,input().split()))
 prefix_sum=[0]
 for i in range(n):
  prefix_sum.append(prefix_sum[-1]+arr[i])
 for i in range(q):
  x,y=map(int,input().split())
  print(prefix_sum[y]-prefix_sum[x-1])

n=int(input())
while(n>0):
 l=list(map(int,input().split()))
 l1=list(map(int,input().split()))
 while(l[1]>0):
  l2=list(map(int,input().split()))
  s=0
  for i in range(l2[0]-1,l2[1]):
   s=s+l1[i]
  print(s)
  l[1]=l[1]-1
 n=n-1


# cook your dish here
def program():
 n,q=map(int, input().split())
 l=list(map(int, input().split()))

 for i in range(q):
  a,b=map(int, input().split())
  print(sum(l[a-1:b]))


t=int(input())
for i in range(t):
 program()