Chef has an array A of length N. In one operation, Chef can:

Choose any subarray [L, R] (1 ≤ L ≤ R ≤ N);
Add 1 to A_{L}, subtract 1 from A_{L+1}, add 1 to A_{L+2}, subtract 1 from A_{L+3} and so on, till A_{R}.

Chef performed Q such operations where the i^{th} operation was performed on the subarray [L_{i}, R_{i}].

Determine the final sum of the array after these Q operations.

Note that a subarray is formed by deleting some (possibly zero) elements from the beginning and some (possibly zero) elements from the end of the array.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two integers N, Q, number of elements and the number of queries.
- The next line contains N space-separated integers A_{1}, A_{2}, \dots A_{N} - denoting the array A.
- The next Q lines contains two space-separated integers with i^{th} line containing L_{i}, R_{i}.

------ Output Format ------ 

For each test case, output the final sum of the array after performing all the Q operations.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N, Q ≤ 3 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 100$
- The sum of $N$ over all test cases won't exceed $3 \cdot 10^{5}$.
- The sum of $Q$ over all test cases won't exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
5 3
1 3 4 4 2
1 5
3 4
2 2
1 2
4
1 1
1 1

----- Sample Output 1 ------ 
16
6

----- explanation 1 ------ 
Test case $1$: The queries are as follows:

- Query $1$: The chosen subarray is $[1, 3, 4, 4, 2]$ which changes to $[1+1, 3-1, 4+1, 4-1, 2+1] = [2, 2, 5, 3, 3]$. Thus, the array becomes $[2, 2, 5, 3, 3]$.
- Query $2$: The chosen subarray is $[5, 3]$ which changes to $[5+1, 3-1] = [6, 2]$. Thus, the array becomes $[2, 2, 6, 2, 3]$.
- Query $3$: The chosen subarray is $[2]$ which changes to $[2+1] = [3]$. Thus, the array becomes $[2, 3, 6, 2, 3]$.

The sum of final array is $2+3+6+2+3 = 16$.

Test case $2$: The queries are as follows:

- Query $1$: The chosen subarray is $[4]$ which changes to $[4+1] = [5]$. Thus, the array becomes $[5]$.
- Query $2$: The chosen subarray is $[5]$ which changes to $[5+1] = [6]$. Thus, the array becomes $[6]$.

The sum of final array is $6$.

Source: codechef | Difficulty: EASY


Solutions:
for i in range(int(input())):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	Ans = sum(A)
	for i in range(Q):
		(L, R) = map(int, input().split())
		oe = R - L + 1
		if oe % 2 == 1:
			Ans += 1
	print(Ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	sum1 = 0
	for j in a:
		sum1 += j
	for i in range(q):
		(r, u) = map(int, input().split())
		if (u - r + 1) % 2:
			sum1 += 1
	print(sum1)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	for i in range(q):
		(l, r) = map(int, input().split())
		if (l - r + 1) % 2 == 1:
			s += 1
	print(s)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	integers = list(map(int, input().split()))
	ans = 0
	for i in range(q):
		(l, r) = map(int, input().split())
		diff = r - l + 1
		if diff % 2 != 0:
			ans += 1
	print(ans + sum(integers))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = sum(list(map(int, input().split())))
	for i in range(q):
		(s, f) = map(int, input().split())
		if (f - s + 1) % 2:
			a += 1
	else:
		print(a)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	for __ in range(q):
		(a, b) = map(int, input().split())
		if (b - a + 1) % 2 == 1:
			s += 1
	print(s)


t = int(input())
for tc in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	c = sum(a)
	for j in range(q):
		(l, r) = map(int, input().split())
		if (l + r) % 2 == 0:
			c += 1
	print(c)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	g = sum(c)
	for i in range(b):
		(e, f) = map(int, input().split())
		if (e + f) % 2 == 0:
			g = g + 1
	print(g)


for t in range(int(input())):
	(n, q) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	sumnum = sum(a)
	for i in range(q):
		(l, r) = map(int, input().split(' '))
		if (r - l) % 2 == 0:
			sumnum = sumnum + 1
	print(sumnum)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for i in range(q):
		(x, y) = map(int, input().split())
		d = x - y + 1
		c += d % 2
	print(sum(a) + c)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split(' '))
	li = list(map(int, input().split(' ')))
	s = sum(li)
	while m > 0:
		(nn, mm) = map(int, input().split(' '))
		c = 1
		if nn == mm:
			s = s + 1
		elif (mm - nn - 1) % 2 == 1:
			s = s + 1
		m = m - 1
	print(s)
	t = t - 1


t = int(input())
for i in range(t):
	(n, q) = input().split()
	n = int(n)
	q = int(q)
	A = [int(x) for x in input().split()]
	count = 0
	sum1 = 0
	for j in range(n):
		sum1 += A[j]
	for j in range(q):
		A = [int(x) for x in input().split()]
		if (A[1] - A[0]) % 2 == 0:
			count += 1
	print(sum1 + count)


t = int(input())
for i in range(t):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	s = 0
	for i in range(N):
		s += A[i]
	for i in range(Q):
		(l, r) = map(int, input().split())
		if (r - l) % 2 == 0:
			s += 1
	print(s)


for i in range(int(input())):
	nandq = input().split()
	n = int(nandq[0])
	q = int(nandq[1])
	arr = input().split()
	count = 0
	for j in range(q):
		landr = input().split()
		l = int(landr[0])
		r = int(landr[1])
		count += (r - l + 1) % 2
	sum = 0
	for i in range(n):
		sum += int(arr[i])
	sum += count
	print(sum)


T = int(input())
for _ in range(T):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = sum(l)
	for i in range(q):
		(a, b) = map(int, input().split())
		if (b - a + 1) % 2 != 0:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	li = list(map(int, input().split()))
	ans = sum(li)
	for i in range(q):
		(l, r) = map(int, input().split())
		ans += (r - l + 1) % 2
	print(ans)


T = int(input())
for _ in range(T):
	(n, q) = map(int, input().split())
	A = list(map(int, input().split()))
	d = 0
	s = 0
	for i in A:
		s += i
	for _ in range(q):
		(l, r) = map(int, input().split())
		if (r - l) % 2 == 0:
			d += 1
	print(s + d)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	d = 0
	sumq = 0
	for i in a:
		sumq += i
	for i in range(q):
		(l, r) = map(int, input().split())
		if (r - l) % 2 == 0:
			d += 1
	total = sumq + d
	print(total)


for i in range(int(input())):
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	d = []
	for j in range(a[1]):
		d.append([int(x) for x in input().split()])
	e = sum(b)
	for j in d:
		if (j[1] - j[0]) % 2 == 0:
			e += 1
	print(e)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	tot = 0
	for i in range(n):
		tot += a[i]
	for j in range(q):
		(l, r) = map(int, input().split())
		if (r - l) % 2 == 0:
			tot += 1
	print(tot)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	t = sum(l)
	for i in range(b):
		(c, d) = map(int, input().split())
		if (d - c + 1) % 2 == 1:
			t += 1
	print(t)


T = int(input())
for i in range(T):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	t = 0
	for i in range(N):
		t += A[i]
	for j in range(Q):
		(a, b) = map(int, input().split())
		if (a - b) % 2 == 0:
			t += 1
	print(t)


T = int(input())
for tc in range(T):
	(n, q) = map(int, input().split())
	arrN = list(map(int, input().split()))
	ans = sum(arrN)
	for i in range(q):
		(l, r) = map(int, input().split())
		if (r - l + 1) % 2 == 1:
			ans += 1
	print(ans)


test_cases = int(input())
for i in range(test_cases):
	(size, queries) = [int(x) for x in input().split()]
	array = [int(y) for y in input().split()]
	s = sum(array)
	for j in range(queries):
		(a, b) = [int(z) for z in input().split()]
		if (b + 1 - a) % 2 == 0:
			s = s
		else:
			s += 1
	print(s)


t = int(input())
while t:
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	for i in range(q):
		(x, y) = map(int, input().split())
		p = y - x + 1
		if p % 2 != 0:
			s += 1
	print(s)
	t -= 1


for I in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	for k in range(b):
		(c, d) = map(int, input().split())
		if (c - d) % 2 == 0:
			s += 1
	print(s)


t = int(input())
while t:
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))[:n]
	sm = sum(arr)
	while q:
		(l, r) = map(int, input().split())
		if (l - r) % 2 == 0:
			sm += 1
		q -= 1
	print(sm)
	t -= 1


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = sum(arr)
	for _ in range(q):
		(l, r) = map(int, input().split())
		if (r - l) % 2 == 0:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = sum(a)
	for i in range(q):
		(c, d) = list(map(int, input().split()))
		if (d - c + 1) % 2 != 0:
			ans += 1
	print(ans)


goals = int(input())
for distractions in range(goals):
	(wife, life) = map(int, input().split())
	aim = list(map(int, input().split()))
	death = 0
	for himakar in range(wife):
		death += aim[himakar]
	for bhasup in range(life):
		(supr, bhav) = map(int, input().split())
		if (bhav - supr) % 2 == 0:
			death += 1
	print(death)


t = int(input())
for x in range(t):
	(n, q) = tuple([int(a) for a in input().split()])
	c = 0
	l = [int(c) for c in input().split()]
	for d in range(q):
		(a, b) = tuple([int(k) for k in input().split()])
		if (b - a) % 2 == 0:
			c += 1
	print(sum(l) + c)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	y = sum(a)
	for _ in range(q):
		(l, r) = map(int, input().split())
		if l == r:
			y += 1
		elif (r - l) % 2 == 0:
			y += 1
	print(y)


t = int(input())
for k in range(0, t):
	(t, q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	extra = 0
	for i in range(0, q):
		(q1, q2) = list(map(int, input().split()))
		if (q2 - q1) % 2 == 0:
			extra = extra + 1
	print(sum(arr) + extra)


import re
for i in range(int(input())):
	(elements, queris) = input().split(' ')
	sum = 0
	for number in re.findall('\\d+', input()):
		sum += int(number)
	for queri in range(int(queris)):
		(start, end) = input().split(' ')
		if (int(end) - int(start) + 1) % 2:
			sum += 1
	print(sum)


T = int(input())
for t in range(T):
	(N, Q) = (int(i) for i in input().split())
	A = [int(i) for i in input().split()]
	res = sum(A)
	for q in range(Q):
		(q1, q2) = (int(i) for i in input().split())
		res += (q2 - q1 + 1) % 2
	print(res)


t = int(input())
for _ in range(t):
	(n, q) = (int(i) for i in input().split())
	arr = [int(j) for j in input().split()]
	s = sum(arr)
	for _ in range(q):
		(st_ind, end_ind) = (int(i) for i in input().split())
		if (end_ind - (st_ind - 1)) % 2 == 1:
			s += 1
	print(s)


nTestCases = int(input())
for testCase in range(nTestCases):
	(nElements, nQueries) = map(int, input().rsplit())
	array = list(map(int, input().rsplit()))
	result = sum(array)
	for query in range(nQueries):
		(fromIdx, toIdx) = map(int, input().rsplit())
		if (toIdx - fromIdx + 1) % 2 != 0:
			result += 1
	print(result)


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	for i in range(q):
		(l, r) = map(int, input().split())
		if (r - l + 1) % 2 == 1:
			s += 1
	print(s)
for t in range(int(input())):
	solve()


no_of_tc = int(input())
for _ in range(no_of_tc):
	(arr_len, no_of_ops) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	tot = 0
	tot += sum(arr)
	for _ in range(no_of_ops):
		(start, end) = map(int, input().split())
		if (end - start) % 2 == 0:
			tot += 1
	print(tot)


testCase = int(input())
while testCase > 0:
	(N, Q) = input().split()
	N = int(N)
	Q = int(Q)
	sum = 0
	for x in input().split():
		sum += int(x)
	for x in range(Q):
		(l, r) = input().split()
		l = int(l)
		r = int(r)
		if (l - r + 1) % 2:
			sum += 1
	print(sum)
	testCase += -1


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	l1 = list(map(int, input().split()))
	s = sum(l1)
	for i in range(b):
		(c, d) = map(int, input().split())
		if (d - c) % 2 == 0:
			s = s + 1
	print(s)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	for i in range(q):
		(a, b) = map(int, input().split())
		if (b - a) % 2 == 0:
			s += 1
	print(s)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	(a, b) = ([], [])
	for i in range(q):
		(l, r) = map(int, input().split())
		if r == 0:
			r = l
		a.append(l)
		b.append(r)
	s = 0
	for j in range(q):
		s += (b[j] - a[j] + 1) % 2
	print(sum(arr) + s)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	(L, R) = ([], [])
	for j in range(0, q):
		(l1, r1) = map(int, input().split())
		if r1 == '':
			r1 = l1
		L.append(l1)
		R.append(r1)
	s = 0
	for b in range(0, q):
		s += (R[b] - L[b] + 1) % 2
	sum1 = sum(l) + s
	print(sum1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(L, R) = ([], [])
	for i in range(k):
		(l, r) = map(int, input().split())
		L.append(l)
		R.append(r)
	s = 0
	for i in range(k):
		s += (R[i] - L[i] + 1) % 2
	print(sum(arr) + s)


for input_var in range(int(input())):
	(_, iterations) = input().split(' ')
	inp_list = list(map(int, input().split(' ')))
	addition = 0
	for _ in range(int(iterations)):
		(x, y) = list(map(int, input().split(' ')))
		if x % 2 != 0 and y % 2 != 0 or (x % 2 == 0 and y % 2 == 0):
			addition += 1
	print(sum(inp_list) + addition)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	c = list(map(int, input().split()))
	t = 0
	for k in range(q):
		(x, y) = list(map(int, input().split()))
		if (y - x + 1) % 2 != 0:
			t += 1
	print(sum(c) + t)