Chef has a sequence of integers A of length N. He creates another sequence B of length 2 \cdot N using sequence A. Initially, B is empty. Chef performs the following process.

For each element A_{i} (1 ≤ i ≤ N) of A:
Choose any arbitrary integer k (Note that the value of k can be different for different elements).
Add A_{i}-k and A_{i}+k to B.

Chef then shuffles the sequence B randomly after this process. 

Since Chef is careless, he lost both A and B and now only vaguely remembers the elements of B. Chef would like to know if the sequence B (which he vaguely remembers) can be correct or not. Can you help him?

Formally, you are provided with a sequence B of size 2 \cdot N. You are required to tell if the provided sequence can be achieved from any sequence A of size N using the given process or not.

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

- The first line of the input contains a single integer T - the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N.
- The second line of each test case contains 2 \cdot N space-separated integers B_{1},B_{2}, \dots,B_{2 \cdot N}.

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

- For each test case, print YES if the provided sequence B can be achieved from any sequence A of size N using the given process. Otherwise, print NO.

You may print each character of YES and NO in uppercase or lowercase (for example, the strings yEs, yes, Yes and YES will be treated identical).

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$ |B| = 2 \cdot N$
$ - 10^{5} ≤ B_{i} ≤ 10^{5}$
- It is guaranteed that the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
1
1 1
2
16 2 2022 2001
2
2 4 -2 4
----- Sample Output 1 ------ 
YES
NO
YES
----- explanation 1 ------ 
- Test case $1$: The given sequence $B$ can be generated using $A = [1]$ with $k=0$ for $A_{1}$.
- Test case $2$: There doesn't exist any sequence $A$ which can generate the given sequence $B$ by simulating the given process.
- Test case $3$: The given sequence $B$ can be generated using $A = [4,0]$ with $k= 0$ for $A_{1}$ and $k=-2$ for $A_{2}$.

Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
t = int(input())
for ni in range(t):
	n = int(input())
	b = [int(i) for i in input().split()]
	if sum(b) % 2 == 0:
		print('YES')
	else:
		print('NO')


def answer():
	n = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	if s & 1:
		print('NO')
	else:
		print('YES')
for test in range(int(input())):
	answer()


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	even = 0
	odd = 0
	for i in range(len(b)):
		if b[i] % 2 != 0:
			odd += 1
		else:
			even += 1
	if even % 2 == 0 and odd % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = input()
	if sum([int(x) for x in input().split()]) % 2:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	odd = 0
	for i in l:
		if i % 2 != 0:
			odd += 1
	if odd % 2 == 0 or odd == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	if s % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	e = []
	o = []
	for i in b:
		if i % 2 == 0:
			e.append(i)
		else:
			o.append(i)
	if len(e) % 2 == 0 and len(o) % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	l = int(input())
	m = 2 * l
	a_l = list(map(int, input().split()))
	odd = 0
	even = 0
	for n in a_l:
		if n % 2 == 0:
			even += 1
		else:
			odd += 1
	if even % 2 == 0 and odd % 2 == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(0, T):
	n = int(input())
	b = list(map(int, input().split()))
	count = 0
	for i in range(0, len(b)):
		if b[i] % 2 == 0:
			count += 1
	if count % 2 == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for x in l:
		if x % 2 != 0:
			l1.append(x)
	if len(l1) % 2 != 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if sum(l) % 2 == 0:
		print('YES')
	else:
		print('NO')


t = input()
for c in range(0, int(t)):
	k = int(input())
	d = list(map(int, input().split()))
	if sum(d) % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	a = int(input())
	arr = list(map(int, input().split()))
	(even, odd) = (0, 0)
	for i in arr:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if even % 2 == 0 and odd % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))[:2 * n]
	odd = 0
	even = 0
	for j in range(2 * n):
		if arr[j] % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd % 2 == 0 and even % 2 == 0:
		print('YES')
	else:
		print('NO')


for hm in range(int(input().strip())):
	a = int(input())
	b = list(map(int, input().strip().split(' ')))
	odd = 0
	even = 0
	for hm in b:
		if hm % 2 == 0:
			even += 1
		else:
			odd += 1
	if even % 2 == 0 and odd % 2 == 0:
		print('YES')
	else:
		print('NO')


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	odd = 0
	even = 0
	for j in arr:
		if j % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd % 2 == 0 and even % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	b = [int(i) for i in input().split()]
	b_sum = sum(b)
	if b_sum % 2 == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	n = int(input())
	op = list(map(int, input().split()))
	even = 0
	odd = 0
	for z in op:
		if z % 2 == 0:
			even += 1
		else:
			odd += 1
	if even % 2 == 0 and odd % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	b = [int(i) for i in input().split()]
	ans = sum(b)
	print('YES') if ans % 2 == 0 else print('NO')
	t -= 1


success = 'YES'
failure = 'NO'

def count_odds(a):
	return sum([x & 1 for x in a])

def count_evens(a):
	return sum([x % 2 == 0 for x in a])

def solve(*args):
	(n, b) = args
	return success if all([count_odds(b) % 2 == 0, count_evens(b) % 2 == 0]) else failure

def do_codechef():
	for t in range(int(input())):
		n = int(input())
		b = list(map(int, input().split(' ')))
		print(solve(n, b))
do_codechef()
exit()


noOfTestCases = int(input())
for _ in range(noOfTestCases):
	N = int(input())
	print('YES') if sum(map(int, input().split())) % 2 == 0 else print('NO')


for hm in range(int(input())):
	a = int(input())
	b = list(map(int, input().strip().split(' ')))
	x = 0
	y = 0
	for hm in b:
		if hm % 2 == 0:
			x += 1
		else:
			y += 1
	if x % 2 == 0 and y % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	odd = 0
	even = 0
	for i in a:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd % 2 == 0 and even % 2 == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	B = list(map(int, input().split()))
	E = []
	O = []
	for i in B:
		if i % 2 == 0:
			E.append(i)
		else:
			O.append(i)
	if len(E) % 2 == len(O) % 2 == 0:
		print('YES')
	else:
		print('NO')


import sys, os
from sys import stdin, stdout
from tkinter import E
io_path = '/Users/kunaldubey/Projects/competitve-programming/IO'
if os.path.exists(io_path):
	sys.stdout = open(io_path + '/output.txt', 'w')
	sys.stdin = open(io_path + '/input.txt', 'r')

def get_ints():
	return map(int, input().strip().split())

def get_ints_list():
	return list(map(int, input().strip().split()))

def get_string():
	return input().strip()
test_cases = int(input())
while test_cases > 0:
	n = int(input())
	arr = get_ints_list()
	sum = 0
	for i in arr:
		sum += i
	if sum % 2 == 0:
		print('YES')
	else:
		print('NO')
	test_cases -= 1


for i in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().split()]
	if sum(A) % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	b = [int(x) for x in input().split(' ')]
	parity_cnt_even = 0
	parity_cnt_odd = 0
	for ele in b:
		if ele % 2 == 0:
			parity_cnt_even += 1
		else:
			parity_cnt_odd += 1
	if parity_cnt_even % 2 == 0 and parity_cnt_odd % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	no = list(map(int, input().split()))
	ce = 0
	cd = 0
	for i in range(2 * n):
		if no[i] % 2 == 0:
			ce += 1
		else:
			cd += 1
	if cd % 2 == 0 and ce % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	N = int(input())
	n = 2 * N
	arr = list(map(int, input().split()))[:n]
	if sum(arr) % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	counte = 0
	counto = 0
	for j in range(len(lst)):
		if lst[j] % 2 == 0:
			counte += 1
		else:
			counto += 1
	if counte % 2 == 0 and counto % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	s = 0
	for j in a:
		s = s + j
	if s % 2 == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	B = [int(k) for k in input().split()]
	B.sort()
	d = 0
	for k in range(2 * n):
		if B[k] % 2:
			d += 1
	if d % 2 == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
while t:
	n = int(input())
	a = [int(i) for i in input().split()]
	d = sum(a)
	if d % 2 == 0:
		print('YES')
	else:
		print('NO')
	t = t - 1


n = int(input())
for i in range(n):
	x = int(input())
	arr = list(map(int, input().split()))
	sum = 0
	for j in arr:
		sum += j
	if sum % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	if s & 1:
		print('NO')
	else:
		print('YES')


t = int(input())
while t > 0:
	n = int(input())
	sum_1 = 0
	li = [int(x) for x in input().split()]
	for i in range(len(li)):
		sum_1 = sum_1 + li[i]
	if sum_1 % 2 == 0:
		print('YES')
	else:
		print('NO')
	t = t - 1


n = int(input())
for i in range(n):
	x = int(input())
	a = list(map(int, input().split()))
	eve = 0
	od = 0
	for i in a:
		if i % 2 == 0:
			eve += 1
		else:
			od += 1
	if eve % 2 == 0 and od % 2 == 0:
		print('YES')
	else:
		print('NO')


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		b = map(int, input().split())
		(even, odd) = (0, 0)
		for j in b:
			if j % 2 == 0:
				even += 1
			else:
				odd += 1
		if even % 2 == 0:
			if odd % 2 == 0:
				print('YES')
			else:
				print('NO')
		else:
			print('NO')
except:
	pass


noOfTestCases = int(input())
for _ in range(noOfTestCases):
	possible = True
	N = int(input())
	numArr = list(map(int, input().split()))
	countDict = {'even': 0, 'odd': 0}
	for num in numArr:
		if num % 2 == 0:
			countDict['even'] += 1
		else:
			countDict['odd'] += 1
	for value in countDict.values():
		if value % 2 != 0:
			possible = False
			print('NO')
			break
	if possible == True:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(odd, even) = (0, 0)
	for val in arr:
		if val % 2 == 0:
			even += 1
		else:
			odd += 1
	if even % 2 == 0 and odd % 2 == 0:
		print('YES')
	else:
		print('NO')


tt = int(input())
for _ in range(tt):
	n = int(input())
	a = list(map(int, input().split()))
	(odds, evens) = (0, 0)
	for x in a:
		if x & 1:
			odds += 1
		else:
			evens += 1
	if odds % 2 == 0 and evens % 2 == 0:
		print('YES')
	else:
		print('NO')