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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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)


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


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)


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


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


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)


t = int(input())
while t > 0:
	t -= 1
	(n, tt) = map(int, input().split())
	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])


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


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


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)


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


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