You are given an array arr[] of n integers and q queries in an array queries[] of length 2*q containing l, r pair for all q queries. You need to compute the following sum over q queries.
 
Array is 0-Indexed.
Example 1:
Input: n = 4
arr = {1, 2, 3, 4}
q = 2
queries = {1, 4, 2, 3}
Output: 10 5
Explaination: In the first query we need sum 
from 1 to 4 which is 1+2+3+4 = 10. In the 
second query we need sum from 2 to 3 which is 
2 + 3 = 5.
Your Task:
You do not need to read input or print anything. Your task is to complete the function querySum() which takes n, arr, q and queries as input parameters and returns the answer for all the queries.
Expected Time Complexity: O(n+q)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ n, q ≤ 1000
1 ≤ arr_{i} ≤ 10^{6}
1 ≤ l ≤ r ≤ n

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def querySum(self, n, arr, q, queries):

        # code here

Solutions:
class Solution:

	def querySum(self, n, arr, q, queries):
		return [sum(arr[queries[i] - 1:queries[i + 1]]) for i in range(0, 2 * q, 2)]


class Node:

	def __init__(self, li, ri):
		(self.li, self.ri) = (li, ri)
		self.sum = 0
		self.l_node = None
		self.r_node = None

class Tree:

	def __init__(self, arr):
		self.arr = arr
		self.root = self._construct_tree()

	def _construct(self, li, ri):
		node = Node(li, ri)
		if li == ri:
			node_sum = self.arr[li]
		else:
			mid = (li + ri) // 2
			(left_node, left_sum) = self._construct(li, mid)
			(right_node, right_sum) = self._construct(mid + 1, ri)
			node.l_node = left_node
			node.r_node = right_node
			node_sum = left_sum + right_sum
		node.sum = node_sum
		return (node, node_sum)

	def _construct_tree(self):
		(root, _) = self._construct(0, len(self.arr) - 1)
		return root

	def _get_sum(self, node, li, ri):
		if node.li == li and node.ri == ri:
			return node.sum
		mid = (node.li + node.ri) // 2
		if ri <= mid:
			return self._get_sum(node.l_node, li, ri)
		elif li > mid:
			return self._get_sum(node.r_node, li, ri)
		else:
			return self._get_sum(node.l_node, li, mid) + self._get_sum(node.r_node, mid + 1, ri)

	def get_sum(self, li, ri):
		return self._get_sum(self.root, li, ri)

class Solution:

	def querySum(self, n, arr, q, queries):
		tree = Tree(arr)
		out = []
		i = 0
		while i < len(queries):
			out.append(tree.get_sum(queries[i] - 1, queries[i + 1] - 1))
			i += 2
		return out


class Solution:

	def querySum(self, n, arr, q, queries):
		prefix_sums = [0] * (n + 1)
		for (i, a) in enumerate(arr):
			prefix_sums[i + 1] = prefix_sums[i] + a
		q_results = [0] * q
		for i in range(q):
			(l, r) = (queries[2 * i], queries[2 * i + 1])
			q_results[i] = prefix_sums[r] - prefix_sums[l - 1]
		return q_results


class Solution:

	def querySum(self, n, arr, q, queries):
		prefix = [0] * (n + 1)
		for i in range(n):
			prefix[i + 1] = prefix[i] + arr[i]
		ans = []
		for j in range(q):
			ans.append(prefix[queries[2 * j + 1]] - prefix[queries[j * 2] - 1])
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		ans = []
		for i in range(1, len(arr)):
			arr[i] += arr[i - 1]
		arr.insert(0, 0)
		for i in range(0, 2 * q, 2):
			ans.append(arr[queries[i + 1]] - arr[queries[i] - 1])
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		add = [0] * n
		add[0] = arr[0]
		ans = []
		for i in range(1, n):
			add[i] = add[i - 1] + arr[i]
		for i in range(1, 2 * q, 2):
			start = queries[i - 1]
			end = queries[i]
			if start == 1:
				ans.append(add[end - 1])
			else:
				ans.append(add[end - 1] - add[start - 2])
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		l = []
		s = 0
		arr2 = []
		for i in arr:
			s += i
			arr2.append(s)
		for i in range(0, len(queries), 2):
			l.append(arr2[queries[i + 1] - 1] - (arr2[queries[i] - 2] if queries[i] - 2 >= 0 else 0))
		return l


class Solution:

	def querySum(self, n, arr, q, queries):
		l = []
		s = 0
		for i in range(0, 2 * q, 2):
			s = 0
			for j in range(queries[i] - 1, queries[i + 1]):
				s += arr[j]
			l.append(s)
		return l


class Solution:

	def querySum(self, n, arr, q, queries):
		r = []
		for i in range(0, len(queries), 2):
			l = arr[queries[i] - 1:queries[i + 1]]
			r.append(sum(l))
		return r


class Solution:

	def querySum(self, n, arr, q, queries):
		res = []
		for i in range(0, 2 * q, 2):
			start = queries[i]
			end = queries[i + 1]
			s = sum(arr[start - 1:end])
			res.append(s)
		return res


class Solution:

	def querySum(self, n, arr, q, queries):
		i = 0
		result = []
		while q > 0:
			(l, r) = (queries[i], queries[i + 1])
			sum = 0
			for k in range(l - 1, r):
				sum += arr[k]
			result.append(sum)
			q -= 1
			i += 2
		return result


class Solution:

	def querySum(self, n, arr, qq, q):
		presum = [0]
		cur_sum = 0
		for i in range(n):
			cur_sum += arr[i]
			presum.append(cur_sum)
		ans = []
		for idx in range(0, 2 * qq, 2):
			(left, right) = (q[idx], q[idx + 1])
			cur_sum = presum[right] - presum[left - 1]
			ans.append(cur_sum)
		return ans


class Solution:

	def querySum(self, n, arr, q, qu):
		s = []
		i = 0
		while i < 2 * q:
			s.append(sum(arr[qu[i] - 1:qu[i + 1]]))
			i += 2
		return s


from bisect import bisect_right

class Solution:

	def querySum(self, n, arr, q, qr):
		ans = list()
		for i in range(0, 2 * q, 2):
			l = qr[i]
			h = qr[i + 1]
			add = 0
			for j in arr[l - 1:h]:
				add += j
			ans.append(add)
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		(l, i) = ([], 0)
		while i < 2 * q - 1:
			if queries[i] - 1 <= queries[i + 1] - 1:
				l.append(sum(arr[queries[i] - 1:queries[i + 1]]))
			i += 2
		return l


class Solution:

	def querySum(self, n, arr, q, queries):
		sums = []
		for i in range(0, len(queries), 2):
			(a, b) = (queries[i], queries[i + 1])
			sum = self.getSum(arr, a - 1, b - 1)
			sums.append(sum)
			i += 1
		return sums

	def getSum(self, arr, a, b):
		sum = 0
		for i in range(a, b + 1):
			sum += arr[i]
		return sum


class SegmentTree:

	def __init__(self, nums):
		self.l = len(nums)
		self.tree = [0] * self.l + self.nums
		for i in range(self.l - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def update(self, i, val):
		n = self.l + i
		self.tree[n] = val
		while n > 1:
			self.tree[n >> 1] = self.tree[n] + self.tree[n ^ 1]
			n >>= 1

	def sumrange(self, i, j):
		m = self.l + i
		n = self.l + j
		res = 0
		while m <= n:
			if m & 1:
				res += self.tree[m]
				m += 1
			m >>= 1
			if n & 1 == 0:
				res += self.tree[n]
				n -= 1
			n >>= 1
		return res
import itertools

class Solution:

	def querySum(self, n, nums, q, queries):
		final = []
		nums = [0] + list(itertools.accumulate(nums))
		for i in range(0, 2 * q, 2):
			(first, last) = (queries[i], queries[i + 1])
			final.append(nums[last] - nums[first - 1])
		return final


class Solution:

	def querySum(self, n, arr, q, queries):
		sumArr = [0]
		sm = 0
		for i in arr:
			sm += i
			sumArr.append(sm)
		res = []
		l = 0
		r = 1
		for i in range(q):
			res.append(sumArr[queries[r]] - sumArr[queries[l] - 1])
			l += 2
			r += 2
		return res


def sasi(a, l, r):
	return sum(a[l - 1:r])

class Solution:

	def querySum(self, n, arr, q, queries):
		b = []
		for i in range(0, q):
			b.append(sasi(arr, queries[2 * i], queries[2 * i + 1]))
		return b


class Solution:

	def querySum(self, n, arr, q, queries):
		t = []
		i = 0
		while i < 2 * q:
			l = queries[i]
			r = queries[i + 1]
			s = sum(arr[l - 1:r])
			t.append(s)
			i += 2
		return t


class Solution:

	def querySum(self, n, arr, q, queries):
		pre = [0] * (n + 1)
		for i in range(1, n + 1):
			pre[i] = pre[i - 1] + arr[i - 1]
		ans = []
		for i in range(q):
			(a, b) = (queries[i * 2], queries[i * 2 + 1])
			ans.append(pre[b] - pre[a - 1])
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		L = []
		for i in range(q):
			a = queries[2 * i] - 1
			b = queries[2 * i + 1]
			L.append(sum(arr[a:b]))
		return L


class Solution:

	def querySum(self, n, arr, q, queries):
		ans = []
		sums = [arr[0]]
		for i in range(1, n):
			sums.append(arr[i] + sums[i - 1])
		for i in range(q):
			l = queries[2 * i] - 1
			r = queries[2 * i + 1] - 1
			if l == 0:
				summ = sums[r]
			else:
				summ = sums[r] - sums[l - 1]
			ans.append(summ)
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		ans = []
		for i in range(q):
			l = queries[2 * i]
			r = queries[2 * i + 1]
			summ = 0
			for j in range(l - 1, r):
				summ += arr[j]
			ans.append(summ)
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		sumArr = [0]
		fsum = 0
		for ele in arr:
			fsum += ele
			sumArr.append(fsum)
		resultArr = []
		i = 0
		while i < 2 * q:
			resultArr.append(sumArr[queries[i + 1]] - sumArr[queries[i] - 1])
			i = i + 2
		return resultArr


class Node:

	def __init__(self, low, high):
		self.low = low
		self.high = high
		self.left = None
		self.right = None
		self.val = 0

class NumArray:

	def __init__(self, nums):
		self.nums = nums
		self.root = self.build(0, len(nums) - 1)

	def build(self, low, high):
		node = Node(low, high)
		if low == high:
			node.val = self.nums[low]
			return node
		mid = (low + high) // 2
		node.left = self.build(low, mid)
		node.right = self.build(mid + 1, high)
		node.val = node.left.val + node.right.val
		return node

	def update(self, idx, val):
		self.updateHelp(idx, val, self.root)

	def updateHelp(self, idx, val, node):
		if node.low == node.high:
			node.val = val
			return
		mid = (node.low + node.high) // 2
		if idx <= mid:
			self.updateHelp(idx, val, node.left)
		else:
			self.updateHelp(idx, val, node.right)
		node.val = node.left.val + node.right.val
		return

	def sumRange(self, left, right):
		return self.sumHelper(left, right, self.root)

	def sumHelper(self, left, right, node):
		if node.low >= left and node.high <= right:
			return node.val
		if right < node.low or left > node.high:
			return 0
		leftSum = self.sumHelper(left, right, node.left)
		rightSum = self.sumHelper(left, right, node.right)
		return leftSum + rightSum

class Solution:

	def querySum(self, n, arr, q, queries):
		numArray = NumArray(arr)
		ans = []
		start = queries[::2]
		end = queries[1::2]
		for i in range(len(start)):
			ans.append(numArray.sumRange(start[i] - 1, end[i] - 1))
		return ans


class Solution:

	def constructTree(self, sgt, arr, ss, se, t):
		if ss == se:
			sgt[t] = arr[ss]
			return sgt[t]
		m = ss + (se - ss) // 2
		sgt[t] = self.constructTree(sgt, arr, ss, m, 2 * t + 1) + self.constructTree(sgt, arr, m + 1, se, 2 * t + 2)
		return sgt[t]

	def createSGTree(self, n, arr):
		sgt = [0 for _ in range(4 * n)]
		self.constructTree(sgt, arr, 0, n - 1, 0)
		return sgt

	def summy(self, sgt, l, r, ss, se, si):
		if l > se or r < ss:
			return 0
		if l <= ss and r >= se:
			return sgt[si]
		m = ss + (se - ss) // 2
		return self.summy(sgt, l, r, ss, m, 2 * si + 1) + self.summy(sgt, l, r, m + 1, se, 2 * si + 2)

	def querySum(self, n, arr, q, queries):
		sgt = self.createSGTree(n, arr)
		res = []
		for i in range(0, len(queries), 2):
			res.append(self.summy(sgt, queries[i] - 1, queries[i + 1] - 1, 0, n - 1, 0))
		return res


class Solution:

	def querySum(self, n, arr, q, queries):
		prefix_sum = [0]
		for num in arr:
			prefix_sum.append(num + prefix_sum[-1])
		answer = []
		for index in range(q):
			(start, end) = (queries[2 * index], queries[2 * index + 1])
			answer.append(prefix_sum[end] - prefix_sum[start - 1])
		return answer


from itertools import accumulate

class Solution:

	def querySum(self, n, arr, q, queries):
		pre = [0] + list(accumulate(arr))
		ans = []
		for i in range(0, 2 * q, 2):
			l = queries[i]
			r = queries[i + 1]
			ans.append(pre[r] - pre[l - 1])
		return ans


from math import log2, ceil

def constructSTUtil(st, arr, ss, se, si):
	mid = (ss + se) // 2
	if ss == se:
		st[si] = arr[ss]
		return st[si]
	st[si] = constructSTUtil(st, arr, ss, mid, 2 * si + 1) + constructSTUtil(st, arr, mid + 1, se, 2 * si + 2)
	return st[si]

def constructST(arr, n):
	h = ceil(log2(n))
	st = [0] * (2 * 2 ** h - 1)
	constructSTUtil(st, arr, 0, n - 1, 0)
	return st

def findSumUtil(st, qs, qe, ss, se, si):
	mid = (ss + se) // 2
	if qe < ss or qs > se:
		return 0
	if qe >= se and qs <= ss:
		return st[si]
	return findSumUtil(st, qs, qe, ss, mid, 2 * si + 1) + findSumUtil(st, qs, qe, mid + 1, se, 2 * si + 2)

class Solution:

	def querySum(self, n, arr, q, queries):
		result = []
		st = constructST(arr, n)
		i = 0
		while i < 2 * q:
			result.append(findSumUtil(st, queries[i] - 1, queries[i + 1] - 1, 0, n - 1, 0))
			i += 2
		return result


class Solution:

	def querySum(self, n, arr, q, queries):
		arrsum = []
		for num in arr:
			if not arrsum:
				arrsum.append(num)
			else:
				arrsum.append(arrsum[-1] + num)
		res = []
		for i in range(0, len(queries) - 1, 2):
			(l, r) = (0, arrsum[queries[i + 1] - 1])
			if queries[i] != 1:
				l = arrsum[queries[i] - 2]
			res.append(r - l)
		return res


import sys
sys.setrecursionlimit(10 ** 6)
ip = sys.stdin.readline
op = sys.stdout.write

class NumArray:

	def __init__(self, arr):
		self.nums = arr
		self.n = len(self.nums)
		self.seg_tree = [0] * (4 * self.n)
		self.build_tree(0, self.n - 1, 1)

	def build_tree(self, start, end, tree_node):
		if start == end:
			self.seg_tree[tree_node] = self.nums[start]
			return
		mid = (start + end) // 2
		self.build_tree(start, mid, tree_node * 2)
		self.build_tree(mid + 1, end, tree_node * 2 + 1)
		self.seg_tree[tree_node] = self.seg_tree[tree_node * 2] + self.seg_tree[tree_node * 2 + 1]

	def update(self, index: int, val: int) -> None:
		self.update_recursively(0, self.n - 1, 1, index, val)

	def update_recursively(self, start, end, tree_node, idx, val):
		if start == end:
			self.nums[idx] = val
			self.seg_tree[tree_node] = val
			return
		mid = (start + end) // 2
		if idx <= mid:
			self.update_recursively(start, mid, tree_node * 2, idx, val)
		else:
			self.update_recursively(mid + 1, end, tree_node * 2 + 1, idx, val)
		self.seg_tree[tree_node] = self.seg_tree[tree_node * 2] + self.seg_tree[tree_node * 2 + 1]

	def query(self, start, end, tree_node, left, right):
		if start > right or end < left:
			return 0
		if start >= left and end <= right:
			return self.seg_tree[tree_node]
		mid = (start + end) // 2
		return self.query(start, mid, 2 * tree_node, left, right) + self.query(mid + 1, end, 2 * tree_node + 1, left, right)

	def SumRange(self, left: int, right: int) -> int:
		return self.query(0, self.n - 1, 1, left, right)

class Solution:

	def querySum(self, n, arr, q, queries):
		segment_tree = NumArray(arr)
		res = []
		for i in range(0, len(queries), 2):
			l = queries[i] - 1
			r = queries[i + 1] - 1
			res.append(segment_tree.SumRange(l, r))
		return res


class Solution:

	def querySum(self, n, arr, q, quer):
		res = []
		for i in range(1, n):
			arr[i] += arr[i - 1]
		arr.insert(0, 0)
		for i in range(0, 2 * q, 2):
			res.append(arr[quer[i + 1]] - arr[quer[i] - 1])
		return res


import math

class Solution:

	def querySum(self, n, arr, q, queries):
		sums = [0] * (2 * 2 ** math.ceil(math.log2(n)))

		def build(l, r, ind):
			if l == r:
				sums[ind] = arr[l]
				return arr[l]
			mid = (l + r) // 2
			sums[ind] = build(l, mid, 2 * ind + 1) + build(mid + 1, r, 2 * ind + 2)
			return sums[ind]
		build(0, n - 1, 0)

		def getsum(l, r, i, j, ind):
			if i > r or j < l:
				return 0
			if i <= l and r <= j:
				return sums[ind]
			mid = (l + r) // 2
			return getsum(l, mid, i, j, 2 * ind + 1) + getsum(mid + 1, r, i, j, 2 * ind + 2)
		build(0, n - 1, 0)
		res = []
		for k in range(q):
			res.append(getsum(0, n - 1, queries[2 * k] - 1, queries[2 * k + 1] - 1, 0))
		return res


import sys
sys.setrecursionlimit(10 ** 6)

class Node(object):

	def __init__(self, start, end):
		self.start = start
		self.end = end
		self.total = 0
		self.left = None
		self.right = None

class NumArray(object):

	def __init__(self, nums):

		def createTree(nums, l, r):
			if l > r:
				return None
			if l == r:
				node = Node(l, r)
				node.total = nums[l]
				return node
			mid = (l + r) // 2
			root = Node(l, r)
			root.left = createTree(nums, l, mid)
			root.right = createTree(nums, mid + 1, r)
			root.total = root.left.total + root.right.total
			return root
		self.root = createTree(nums, 0, len(nums) - 1)

	def update(self, i, val):

		def updateVal(root, i, val):
			if root.start == root.end:
				root.total = val
				return val
			mid = (root.start + root.end) // 2
			if i <= mid:
				updateVal(root.left, i, val)
			else:
				updateVal(root.right, i, val)
			root.total = root.left.total + root.right.total
			return root.total
		return updateVal(self.root, i, val)

	def sumRange(self, i, j):

		def rangeSum(root, i, j):
			if root.start == i and root.end == j:
				return root.total
			mid = (root.start + root.end) // 2
			if j <= mid:
				return rangeSum(root.left, i, j)
			elif i >= mid + 1:
				return rangeSum(root.right, i, j)
			else:
				return rangeSum(root.left, i, mid) + rangeSum(root.right, mid + 1, j)
		return rangeSum(self.root, i, j)

class Solution:

	def querySum(self, n, nums, q, queries):
		segment_tree = NumArray(nums)
		res = []
		for i in range(0, len(queries), 2):
			l = queries[i]
			r = queries[i + 1]
			res.append(segment_tree.sumRange(l - 1, r - 1))
		return res


class Solution:

	def querySum(self, n, arr, q, queries):
		ans = [0] * n
		ans[0] = arr[0]
		res = [0] * q
		for i in range(1, n):
			ans[i] = ans[i - 1] + arr[i]
		for i in range(0, 2 * q, 2):
			if queries[i] - 2 == -1:
				res[i // 2] = ans[queries[i + 1] - 1]
			else:
				res[i // 2] = ans[queries[i + 1] - 1] - ans[queries[i] - 2]
		return res


class Solution:

	def querySum(self, n, arr, q, queries):
		ar = []
		dp = [0]
		s = 0
		for it in arr:
			s += it
			dp.append(s)
		i = 0
		while i < 2 * q:
			x = queries[i] - 1
			y = queries[i + 1]
			tem = dp[y] - dp[x]
			ar.append(tem)
			i += 2
		return ar


class Solution:

	def querySum(self, n, arr, q, queries):
		a = [0] + arr
		for i in range(n):
			a[i + 1] += a[i]
		ans = []
		for qq in range(q):
			ans += [a[queries[2 * qq + 1]] - a[queries[2 * qq] - 1]]
		return ans


class Solution:

	def querySum(self, n, arr, q, qs):
		b = []
		i = 0
		j = 2 * q
		while i < j:
			b.append(sum(arr[qs[i] - 1:qs[i + 1]]))
			i += 2
		return b


class Solution:

	def querySum(self, n, arr, q, queries):
		cumsum_arr = [0]
		cumsum = 0
		for i in range(n):
			cumsum += arr[i]
			cumsum_arr.append(cumsum)
		output = []
		for i in range(q):
			output.append(cumsum_arr[queries[2 * i + 1]] - cumsum_arr[queries[2 * i] - 1])
		return output


class Solution:

	def querySum(self, n, arr, q, queries):
		prefix_sum = [0]
		for i in arr:
			prefix_sum.append(prefix_sum[-1] + i)
		ans = []
		for i in range(0, 2 * q, 2):
			l = queries[i]
			r = queries[i + 1]
			ans.append(prefix_sum[r] - prefix_sum[l - 1])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = input().split()
		for i in range(n):
			arr[i] = int(arr[i])
		q = int(input())
		queries = input().split()
		for i in range(0, 2 * q, 2):
			queries[i] = int(queries[i])
			queries[i + 1] = int(queries[i + 1])
		ob = Solution()
		ans = ob.querySum(n, arr, q, queries)
		for it in ans:
			print(it, end=' ')
		print()


from typing import List

class SegmentTree:

	def __init__(self, arr: List[int]) -> None:
		self.segment_tree = [0] * (4 * len(arr))
		self.L = 0
		self.R = len(arr) - 1
		self.build(arr, self.L, self.R, 0)

	def build(self, arr: List[int], l: int, r: int, index: int) -> int:
		if l == r:
			self.segment_tree[index] = arr[l]
			return self.segment_tree[index]
		m = l + (r - l) // 2
		self.segment_tree[index] = self.build(arr, l, m, 2 * index + 1) + self.build(arr, m + 1, r, 2 * index + 2)
		return self.segment_tree[index]

	def _update(self, index: int, l: int, r: int, pos: int, value: int) -> None:
		if l == r:
			self.segment_tree[index] = value
			return
		m = l + (r - l) // 2
		if pos >= l and pos <= m:
			self._update(2 * index + 1, l, m, pos, value)
		else:
			self._update(2 * index + 2, m + 1, r, pos, value)
		self.segment_tree[index] = self.segment_tree[2 * index + 1] + self.segment_tree[2 * index + 2]

	def update(self, pos: int, value: int):
		self._update(0, self.L, self.R, pos, value)

	def _query(self, l: int, r: int, L: int, R: int, index: int) -> int:
		if l == L and r == R:
			return self.segment_tree[index]
		M = L + (R - L) // 2
		if r <= M:
			return self._query(l, r, L, M, 2 * index + 1)
		elif l > M:
			return self._query(l, r, M + 1, R, 2 * index + 2)
		else:
			return self._query(l, M, L, M, 2 * index + 1) + self._query(M + 1, r, M + 1, R, 2 * index + 2)

	def query(self, l: int, r: int) -> int:
		return self._query(l, r, self.L, self.R, 0)

class Solution:

	def querySum(self, n, arr, q, queries):
		st = SegmentTree(arr)
		ret = []
		for i in range(q):
			ans = st.query(queries[i * 2] - 1, queries[i * 2 + 1] - 1)
			ret.append(ans)
		return ret
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = input().split()
		for i in range(n):
			arr[i] = int(arr[i])
		q = int(input())
		queries = input().split()
		for i in range(0, 2 * q, 2):
			queries[i] = int(queries[i])
			queries[i + 1] = int(queries[i + 1])
		ob = Solution()
		ans = ob.querySum(n, arr, q, queries)
		for it in ans:
			print(it, end=' ')
		print()


class Solution:

	def querySum(self, n, arr, q, queries):
		seg = [0] * (4 * n)

		def build(index, low, high):
			if low == high:
				seg[index] = arr[low]
				return
			mid = (low + high) // 2
			build(2 * index + 1, low, mid)
			build(2 * index + 2, mid + 1, high)
			seg[index] = seg[2 * index + 1] + seg[2 * index + 2]

		def query(index, low, high, l, r):
			if high < l or r < low:
				return 0
			elif low >= l and high <= r:
				return seg[index]
			else:
				mid = (low + high) // 2
				le = query(2 * index + 1, low, mid, l, r)
				re = query(2 * index + 2, mid + 1, high, l, r)
				return le + re
		build(0, 0, n - 1)
		ans = []
		i = 0
		while i < 2 * q:
			a = queries[i]
			b = queries[i + 1]
			ans.append(query(0, 0, n - 1, a - 1, b - 1))
			i = i + 2
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = input().split()
		for i in range(n):
			arr[i] = int(arr[i])
		q = int(input())
		queries = input().split()
		for i in range(0, 2 * q, 2):
			queries[i] = int(queries[i])
			queries[i + 1] = int(queries[i + 1])
		ob = Solution()
		ans = ob.querySum(n, arr, q, queries)
		for it in ans:
			print(it, end=' ')
		print()


class Solution:

	def build(self, l, r, idx, segment, arr):
		if l == r:
			segment[idx] = arr[l]
			return
		mid = (l + r) // 2
		self.build(l, mid, 2 * idx + 1, segment, arr)
		self.build(mid + 1, r, 2 * idx + 2, segment, arr)
		segment[idx] = segment[2 * idx + 1] + segment[2 * idx + 2]

	def query(self, ss, se, idx, segment, qs, qe):
		if qs > se or qe < ss:
			return 0
		elif qs <= ss and qe >= se:
			return segment[idx]
		else:
			mid = (ss + se) // 2
			return self.query(ss, mid, 2 * idx + 1, segment, qs, qe) + self.query(mid + 1, se, 2 * idx + 2, segment, qs, qe)

	def querySum(self, n, arr, q, queries):
		segment = [0] * 4 * n
		self.build(0, n - 1, 0, segment, arr)
		ans = []
		for i in range(0, q * 2, 2):
			qs = queries[i]
			qe = queries[i + 1]
			ans.append(self.query(0, n - 1, 0, segment, qs - 1, qe - 1))
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = input().split()
		for i in range(n):
			arr[i] = int(arr[i])
		q = int(input())
		queries = input().split()
		for i in range(0, 2 * q, 2):
			queries[i] = int(queries[i])
			queries[i + 1] = int(queries[i + 1])
		ob = Solution()
		ans = ob.querySum(n, arr, q, queries)
		for it in ans:
			print(it, end=' ')
		print()


class Solution:

	def construct(self, tree, arr, start, end, ind):
		if start == end:
			tree[ind] = arr[start]
			return
		mid = (start + end) // 2
		self.construct(tree, arr, start, mid, 2 * ind + 1)
		self.construct(tree, arr, mid + 1, end, 2 * ind + 2)
		tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2]
		return

	def query(self, tree, start, end, low, high, ind):
		if high < start or low > end:
			return 0
		if low <= start and end <= high:
			return tree[ind]
		mid = (start + end) // 2
		return self.query(tree, start, mid, low, high, 2 * ind + 1) + self.query(tree, mid + 1, end, low, high, 2 * ind + 2)

	def update(self, tree, arr, start, end, ind, upd_ind, val):
		if start == upd_ind:
			tree[ind] = val
			arr[start] = val
			return
		mid = (start + end) // 2
		if mid >= ind:
			self.update(tree, arr, start, mid, 2 * ind + 1, upd_ind, val)
		else:
			self.update(tree, arr, mid + 1, end, 2 * ind + 2, upd_ind, val)
		tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2]
		return

	def querySum(self, n, arr, q, queries):
		ans = []
		tree = [0] * (4 * n)
		self.construct(tree, arr, 0, n - 1, 0)
		for i in range(0, 2 * q, 2):
			ans.append(self.query(tree, 0, n - 1, queries[i] - 1, queries[i + 1] - 1, 0))
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = input().split()
		for i in range(n):
			arr[i] = int(arr[i])
		q = int(input())
		queries = input().split()
		for i in range(0, 2 * q, 2):
			queries[i] = int(queries[i])
			queries[i + 1] = int(queries[i + 1])
		ob = Solution()
		ans = ob.querySum(n, arr, q, queries)
		for it in ans:
			print(it, end=' ')
		print()


class Solution:

	def getsum(self, l, r, st, start, end, pos):
		if l <= start and end <= r:
			return st[pos]
		if end < l or start > r:
			return 0
		mid = (start + end) // 2
		return self.getsum(l, r, st, start, mid, 2 * pos + 1) + self.getsum(l, r, st, mid + 1, end, 2 * pos + 2)

	def makest(self, arr, st, start, end, pos):
		if start == end:
			st[pos] = arr[start]
			return st[pos]
		mid = (start + end) // 2
		st[pos] = self.makest(arr, st, start, mid, 2 * pos + 1) + self.makest(arr, st, mid + 1, end, 2 * pos + 2)
		return st[pos]

	def querySum(self, n, arr, q, queries):
		from math import log2, ceil
		n = len(arr)
		size = 2 * 2 ** ceil(log2(n)) - 1
		st = [0] * size
		self.makest(arr, st, 0, n - 1, 0)
		ans = []
		for i in range(0, len(queries), 2):
			l = queries[i] - 1
			r = queries[i + 1] - 1
			ans.append(self.getsum(l, r, st, 0, n - 1, 0))
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = input().split()
		for i in range(n):
			arr[i] = int(arr[i])
		q = int(input())
		queries = input().split()
		for i in range(0, 2 * q, 2):
			queries[i] = int(queries[i])
			queries[i + 1] = int(queries[i + 1])
		ob = Solution()
		ans = ob.querySum(n, arr, q, queries)
		for it in ans:
			print(it, end=' ')
		print()


class Solution:

	def querySum(self, n, arr, q, queries):
		tree = [0 for i in range(4 * n)]

		def construct(li, ri, index):
			if li == ri:
				tree[index] = arr[li]
				return arr[li]
			mid = (li + ri) // 2
			tree[index] = construct(li, mid, 2 * index + 1) + construct(mid + 1, ri, 2 * index + 2)
			return tree[index]

		def get_sum(li, ri, ss, se, index):
			if se < li or ss > ri:
				return 0
			if ss <= li and ri <= se:
				return tree[index]
			mid = (li + ri) // 2
			return get_sum(li, mid, ss, se, 2 * index + 1) + get_sum(mid + 1, ri, ss, se, 2 * index + 2)
		construct(0, len(arr) - 1, 0)
		ans = []
		for i in range(0, 2 * q, 2):
			ans.append(get_sum(0, len(arr) - 1, queries[i] - 1, queries[i + 1] - 1, 0))
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = input().split()
		for i in range(n):
			arr[i] = int(arr[i])
		q = int(input())
		queries = input().split()
		for i in range(0, 2 * q, 2):
			queries[i] = int(queries[i])
			queries[i + 1] = int(queries[i + 1])
		ob = Solution()
		ans = ob.querySum(n, arr, q, queries)
		for it in ans:
			print(it, end=' ')
		print()


import math

class SegmentTree:

	def __init__(self, array):
		self.array = array
		self.n = len(self.array)
		height = int(math.ceil(math.log2(self.n)))
		maxSize = 2 * int(2 ** height) + 1
		self.tree = [0] * maxSize
		self.constructSTUtility(self.array, 0, self.n - 1, self.tree, 0)

	def constructSTUtility(self, arr, start, end, tree, segTreeIndex):
		if start == end:
			tree[segTreeIndex] = arr[start]
			return arr[start]
		mid = start + (end - start) // 2
		tree[segTreeIndex] = self.constructSTUtility(arr, start, mid, tree, 2 * segTreeIndex + 1) + self.constructSTUtility(arr, mid + 1, end, tree, 2 * segTreeIndex + 2)
		return tree[segTreeIndex]

	def showTree(self):
		print(self.tree)

	def Query(self, start, end, query):
		if query == 'sum':
			return self.getSum(start, end)

	def getSum(self, start, end):
		if start < 0 or end > self.n - 1 or start > end:
			return 'Invalid Input'
		else:
			return self.getSumUtil(start, end, 0, self.n - 1, 0)

	def getSumUtil(self, queryStart, queryEnd, currentStart, currentEnd, currentSegTreeIndex):
		if queryStart <= currentStart and queryEnd >= currentEnd:
			return self.tree[currentSegTreeIndex]
		if queryStart > currentEnd or queryEnd < currentStart:
			return 0
		mid = currentStart + (currentEnd - currentStart) // 2
		return self.getSumUtil(queryStart, queryEnd, currentStart, mid, 2 * currentSegTreeIndex + 1) + self.getSumUtil(queryStart, queryEnd, mid + 1, currentEnd, 2 * currentSegTreeIndex + 2)

class Solution:

	def querySum(self, n, arr, q, queries):
		sg = SegmentTree(arr)
		output = list()
		for i in range(0, q, 1):
			start = queries[2 * i] - 1
			end = queries[2 * i + 1] - 1
			output.append(sg.Query(start, end, 'sum'))
		return output


class Solution:

	def querySum(self, n, arr, q, queries):
		seg = [0] * 10 ** 5

		def build(i, l, h):
			if l == h:
				seg[i] = arr[l]
				return
			mid = (l + h) // 2
			build(2 * i + 1, l, mid)
			build(2 * i + 2, 1 + mid, h)
			seg[i] = seg[2 * i + 1] + seg[2 * i + 2]

		def qu(i, low, high, l, r):
			if low >= l and high <= r:
				return seg[i]
			if low > r or high < l:
				return 0
			mid = (low + high) // 2
			left = qu(2 * i + 1, low, mid, l, r)
			right = qu(2 * i + 2, 1 + mid, high, l, r)
			return left + right
		build(0, 0, n - 1)
		ans = []
		for i in range(0, 2 * q, 2):
			ans.append(qu(0, 0, n - 1, queries[i] - 1, queries[i + 1] - 1))
		return ans


class Node(object):

	def __init__(self, start, end):
		self.start = start
		self.end = end
		self.total = 0
		self.left = None
		self.right = None

class Solution:

	def __init__(self):
		self.t = 0

	def querySum(self, n, nums, q, qu):

		def createTree(nums, l, r):
			if l == r:
				n = Node(l, r)
				n.total = nums[l]
				return n
			mid = (l + r) // 2
			root = Node(l, r)
			root.left = createTree(nums, l, mid)
			root.right = createTree(nums, mid + 1, r)
			root.total = root.left.total + root.right.total
			return root
		root = createTree(nums, 0, len(nums) - 1)

		def rangeSum(root, i, j):
			if root.start == i and root.end == j:
				return root.total
			mid = (root.start + root.end) // 2
			if j <= mid:
				return rangeSum(root.left, i, j)
			elif i >= mid + 1:
				return rangeSum(root.right, i, j)
			else:
				return rangeSum(root.left, i, mid) + rangeSum(root.right, mid + 1, j)
		ans = []
		for i in range(0, len(qu), 2):
			ans.append(rangeSum(root, qu[i] - 1, qu[i + 1] - 1))
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		compsum = [arr[0]]
		for i in range(1, n):
			compsum.append(compsum[-1] + arr[i])
		res = []
		for i in range(0, 2 * q, 2):
			l = queries[i]
			r = queries[i + 1]
			res.append(compsum[r - 1] - (compsum[l - 2] if l > 1 else 0))
		return res


class Solution:

	def querySum(self, n, arr, q, queries):
		prefix_sum = [0] * n
		result = []
		for (i, elem) in enumerate(arr):
			if i == 0:
				prefix_sum[i] = elem
			else:
				prefix_sum[i] = prefix_sum[i - 1] + elem
		for i in range(0, 2 * q, 2):
			(left, right) = (queries[i] - 1, queries[i + 1] - 1)
			result.append(prefix_sum[right] - prefix_sum[left] + arr[left])
		return result


from math import ceil, log2

def getMid(s, e):
	return s + (e - s) // 2

def getSumUtil(st, ss, se, qs, qe, si):
	if qs <= ss and qe >= se:
		return st[si]
	if se < qs or ss > qe:
		return 0
	mid = getMid(ss, se)
	return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2)

def updateValueUtil(st, ss, se, i, diff, si):
	if i < ss or i > se:
		return
	st[si] = st[si] + diff
	if se != ss:
		mid = getMid(ss, se)
		updateValueUtil(st, ss, mid, i, diff, 2 * si + 1)
		updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2)

def updateValue(arr, st, n, i, new_val):
	if i < 0 or i > n - 1:
		print('Invalid Input', end='')
		return
	diff = new_val - arr[i]
	arr[i] = new_val
	updateValueUtil(st, 0, n - 1, i, diff, 0)

def getSum(st, n, qs, qe):
	if qs < 0 or qe > n - 1 or qs > qe:
		print('Invalid Input', end='')
		return -1
	return getSumUtil(st, 0, n - 1, qs, qe, 0)

def constructSTUtil(arr, ss, se, st, si):
	if ss == se:
		st[si] = arr[ss]
		return arr[ss]
	mid = getMid(ss, se)
	st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) + constructSTUtil(arr, mid + 1, se, st, si * 2 + 2)
	return st[si]

def constructST(arr, n):
	x = int(ceil(log2(n)))
	max_size = 2 * int(2 ** x) - 1
	st = [0] * max_size
	constructSTUtil(arr, 0, n - 1, st, 0)
	return st

class Solution:

	def querySum(self, n, arr, q, queries):
		st = constructST(arr, n)
		ansOfSum = []
		for i in range(q):
			ansOfSum.append(getSum(st, n, queries[2 * i] - 1, queries[2 * i + 1] - 1))
		return ansOfSum


class Solution:

	def querySum(self, n, arr, q, queries):
		ele = []
		for i in range(2 * q):
			if i % 2 == 0:
				queries[i] = queries[i] - 1
		for i in range(0, 2 * q, 2):
			sumi = sum(arr[queries[i]:queries[i + 1]])
			ele.append(sumi)
		return ele


class Solution:

	def querySum(self, n, arr, q, queries):
		result = []
		for i in range(q):
			current = i * 2
			fr = queries[current] - 1
			to = queries[current + 1]
			result.append(sum(arr[fr:to]))
		return result


class Solution:

	def querySum(self, n, arr, q, queries):
		dp = [0] * (n + 1)
		for (i, v) in enumerate(arr):
			dp[i + 1] = dp[i] + arr[i]
		ans = []
		for i in range(q):
			l = queries[2 * i]
			r = queries[2 * i + 1]
			ans.append(dp[r] - dp[l - 1])
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		prefixSum = [0] * (n + 1)
		for i in range(1, n + 1):
			prefixSum[i] = prefixSum[i - 1] + arr[i - 1]
		result = []
		for i in range(1, len(queries), 2):
			result.append(prefixSum[queries[i]] - prefixSum[queries[i - 1] - 1])
		return result


class SegmentTree:

	def __init__(self, arr):
		self.n = len(arr)
		self.tree = [0] * self.n + arr
		for i in range(self.n - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def sumRange(self, l, r):
		l += self.n
		r += self.n
		res = 0
		while l <= r:
			if l & 1:
				res += self.tree[l]
				l += 1
			if not r & 1:
				res += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return res

class Solution:

	def querySum(self, n, arr, q, queries):
		st = SegmentTree(arr)
		res = []
		for i in range(1, len(queries), 2):
			l = queries[i - 1] - 1
			r = queries[i] - 1
			res.append(st.sumRange(l, r))
		return res


class Solution:

	def querySum(self, n, arr, q, queries):
		prefix = [0]
		for v in arr:
			prefix.append(prefix[-1] + v)
		res = []
		for i in range(1, len(queries), 2):
			l = queries[i - 1] - 1
			r = queries[i] - 1
			res.append(prefix[r + 1] - prefix[l])
		return res


class Solution:

	def querySum(self, n, arr, q, queries):
		l1 = []
		for i in range(0, 2 * q, 2):
			l = queries[i]
			r = queries[i + 1]
			sum1 = 0
			for j in range(l - 1, r, 1):
				sum1 += arr[j]
			l1.append(sum1)
		return l1


class Solution:

	def querySum(self, n, arr, q, queries):
		for i in range(1, len(arr)):
			arr[i] += arr[i - 1]
		ans = []
		for (l, r) in zip(queries[::2], queries[1::2]):
			lval = arr[l - 2] if l >= 2 else 0
			rval = arr[r - 1]
			ans.append(rval - lval)
		return ans


import math

class Solution:

	def querySum(self, n, arr, q, queries):
		result = []
		for i in range(0, 2 * q - 1, 2):
			l = queries[i] - 1
			r = queries[i + 1]
			result.append(sum(arr[l:r]))
		return result


class Solution:

	def querySum(self, n, arr, q, queries):
		cumsum = []
		s = 0
		for e in arr:
			s = s + e
			cumsum = cumsum + [s]
		ans = []
		for i in range(0, 2 * q, 2):
			(x, y) = (queries[i] - 1, queries[i + 1] - 1)
			ans = ans + [cumsum[y] - cumsum[x] + arr[x]]
		return ans


class Solution:

	def querySum(self, n, arr, q, queries):
		ans = []
		for i in range(0, 2 * q - 1, 2):
			left = queries[i] - 1
			right = queries[i + 1]
			ans.append(sum(arr[left:right]))
		return ans


class Solution:

	def querySum(self, n, arr, q, qu):
		ps = [0]
		s = 0
		for i in arr:
			s += i
			ps.append(s)
		res = []
		for i in range(0, 2 * q, 2):
			(l, r) = (qu[i], qu[i + 1])
			res.append(ps[r] - ps[l - 1])
		return res