A picture can be represented as an $n\times m$ grid ($n$ rows and $m$ columns) so that each of the $n \cdot m$ cells is colored with one color. You have $k$ pigments of different colors. You have a limited amount of each pigment, more precisely you can color at most $a_i$ cells with the $i$-th pigment.

A picture is considered beautiful if each cell has at least $3$ toroidal neighbors with the same color as itself.

Two cells are considered toroidal neighbors if they toroidally share an edge. In other words, for some integers $1 \leq x_1,x_2 \leq n$ and $1 \leq y_1,y_2 \leq m$, the cell in the $x_1$-th row and $y_1$-th column is a toroidal neighbor of the cell in the $x_2$-th row and $y_2$-th column if one of following two conditions holds:

$x_1-x_2 \equiv \pm1 \pmod{n}$ and $y_1=y_2$, or

$y_1-y_2 \equiv \pm1 \pmod{m}$ and $x_1=x_2$.

Notice that each cell has exactly $4$ toroidal neighbors. For example, if $n=3$ and $m=4$, the toroidal neighbors of the cell $(1, 2)$ (the cell on the first row and second column) are: $(3, 2)$, $(2, 2)$, $(1, 3)$, $(1, 1)$. They are shown in gray on the image below:

The gray cells show toroidal neighbors of $(1, 2)$.

Is it possible to color all cells with the pigments provided and create a beautiful picture?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($3 \leq n,m \leq 10^9$, $1 \leq k \leq 10^5$) — the number of rows and columns of the picture and the number of pigments.

The next line contains $k$ integers $a_1,a_2,\dots, a_k$ ($1 \leq a_i \leq 10^9$) — $a_i$ is the maximum number of cells that can be colored with the $i$-th pigment.

It is guaranteed that the sum of $k$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print "Yes" (without quotes) if it is possible to color a beautiful picture. Otherwise, print "No" (without quotes).


-----Examples-----

Input
6
4 6 3
12 9 8
3 3 2
8 8
3 3 2
9 5
4 5 2
10 11
5 4 2
9 11
10 10 3
11 45 14
Output
Yes
No
Yes
Yes
No
No


-----Note-----

In the first test case, one possible solution is as follows:

In the third test case, we can color all cells with pigment $1$.

Source: codeforces | Difficulty: MEDIUM
Tags: Greedy algorithms

Mathematics

Constructive algorithms


Solutions:
import sys

def solve1(n, m, a):
	s = 0
	ok = False
	for i in a:
		v = i // m
		if v >= 2:
			s += v
			if v > 2:
				ok = True
	if ok:
		return s >= n
	else:
		return s >= n and n % 2 == 0

def solve():
	inp = sys.stdin.readline
	(n, m, k) = map(int, inp().split())
	a = list(map(int, inp().split()))
	if solve1(n, m, a) or solve1(m, n, a):
		print('Yes')
	else:
		print('No')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from sys import stdin, stdout

def get_ints():
	return map(int, stdin.readline().split())

def PRINT(s):
	stdout.write(s + '\n')

def f(a, b, arr):
	evens = []
	odds = []
	s = 0
	t = False
	for v in arr:
		x = v // a
		if x >= 2:
			s += x
			if x % 2 == 0:
				evens.append(x)
			else:
				odds.append(x)
			if x >= 4:
				t = True
	L = len(odds)
	if not t and b % 2 == 1 and (L == 0):
		return False
	if b % 2 == 0 and L % 2 == 1 or (b % 2 == 1 and L % 2 == 0):
		s -= 1
	if s >= b:
		return True
	return False

def logic(n, m, arr):
	if f(n, m, arr) or f(m, n, arr):
		return 'Yes'
	return 'No'
for w in range(int(stdin.readline())):
	(n, m, k) = get_ints()
	arr = [int(x) for x in stdin.readline().split()]
	print(logic(n, m, arr))


import collections
import sys

class Solver(collections.namedtuple('Solver', ('n', 'm', 'k', 'volumes'))):

	@classmethod
	def read(cls, fin):
		(n, m, k) = map(int, fin.readline().split())
		volumes = list(map(int, fin.readline().split()))
		return cls(n, m, k, volumes)

	def try_vertical(self, transpose=False):
		(n, m) = (self.n, self.m)
		if transpose:
			(n, m) = (m, n)

		def get_max_width(volume):
			if (width := (volume // n)) >= 2:
				return width
			return 0
		widths = list(map(get_max_width, self.volumes))
		if all(map(lambda x: x <= 2, widths)) and m % 2 == 1:
			return False
		return sum(widths) >= m

	def solve(self):
		return self.try_vertical() or self.try_vertical(transpose=True)

def main():
	if '--local-run' in sys.argv:
		fin = open('input.txt', 'r')
		fout = open('output.txt', 'w')
	else:
		fin = sys.stdin
		fout = sys.stdout
	num = int(fin.readline())
	for i in range(num):
		print('Yes' if Solver.read(fin).solve() else 'No', file=fout)
main()


def solve(n, m):
	s = 0
	cut = False
	for i in a:
		t = i // n
		if t >= 2:
			s += t
			if t > 2 and (not cut):
				cut = True
	return s >= m and (m % 2 == 0 or cut)
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print('Yes' if solve(n, m) or solve(m, n) else 'No')


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	(*a,) = map(int, input().split())
	b = []
	c = []
	bodd = 0
	codd = 0
	for e in a:
		bi = e // n
		bi = bi * (bi >= 2)
		ci = e // m
		ci = ci * (ci >= 2)
		bodd |= bi >= 3
		codd |= ci >= 3
		b += [bi]
		c += [ci]
	sb = sum(b)
	sc = sum(c)
	o = ''
	if sb >= m and (m & 1 == 0 or bodd) or (sc >= n and (n & 1 == 0 or codd)):
		o = 'Yes'
	else:
		o = 'No'
	print(o)


t = int(input())

def solve(n, m):
	res = 0
	for i in piles:
		u = i // n
		if u > 1:
			res += u
		if res >= m:
			if res - u == m - 1:
				return piles[0] // n > 2
			return True
	return False
for _ in range(t):
	(n, m, k) = map(int, input().split())
	piles = sorted(map(int, input().split()), reverse=True)
	if solve(n, m) or solve(m, n):
		print('Yes')
	else:
		print('No')


def possible(xs, m, n):
	ys = [x // m for x in xs]
	ys = [y for y in ys if y > 1]
	if len(ys) == 0 or sum(ys) < n:
		return False
	return max(ys) >= 3 or n % 2 == 0

def solve():
	(n, m, k) = map(int, input().split())
	xs = [int(x) for x in input().split()]
	if possible(xs, m, n) or possible(xs, n, m):
		print('Yes')
	else:
		print('No')

def main():
	T = int(input().strip())
	for t in range(1, T + 1):
		solve()
main()


R = lambda : map(int, input().split())
G = range
(t,) = R()

def f(n, m):
	b = [v // n for v in a if v >= 2 * n]
	return not (m & 1 and all((v == 2 for v in b))) and sum(b) >= m
for _ in G(t):
	(n, m, k) = R()
	a = [*R()]
	print(['No', 'Yes'][f(n, m) or f(m, n)])


def solve(n, m, arr):
	p = m
	curr = 0
	flag = False
	for i in arr:
		k = i // p
		if k > 1:
			curr += k
		if k > 2:
			flag = True
	if n % 2 == 0:
		if curr >= n:
			return True
		else:
			return False
	elif curr >= n and flag:
		return True
	else:
		return False
t = int(input())
while t:
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	a = solve(n, m, arr)
	b = solve(m, n, arr)
	if a or b:
		print('Yes')
	else:
		print('No')
	t -= 1


standard_input = '6\n4 6 3\n12 9 8\n3 3 2\n8 8\n3 3 2\n9 5\n4 5 2\n10 11\n5 4 2\n9 11\n10 10 3\n11 45 14\n'

def isPossible(major, minor, colors):
	usable = []
	canDoOdd = False
	for i in colors:
		col = i // major
		if col >= 2:
			usable.append(col)
		if col >= 3:
			canDoOdd = True
	return sum(usable) >= minor and (minor % 2 == 0 or canDoOdd)
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print('Yes' if isPossible(n, m, a) or isPossible(m, n, a) else 'No')


import bisect
x = int(input())

def cal(n, m, k, arr):
	arr.sort()
	if arr[-1] >= n * m:
		return True
	t = bisect.bisect_left(arr, n * 2)
	if t < k:
		ck = 0
		thr = 0
		for i in range(t, k):
			a = arr[i] // n
			if a > 2:
				thr += 1
			ck += a
		if ck >= m:
			if thr > 0:
				return True
			elif m % 2 == 0:
				return True
	(n, m) = (m, n)
	t = bisect.bisect_left(arr, n * 2)
	if t < k:
		ck = 0
		thr = 0
		for i in range(t, k):
			a = arr[i] // n
			if a > 2:
				thr += 1
			ck += a
		if ck >= m:
			if thr > 0:
				return True
			elif m % 2 == 0:
				return True
	return False
for jj in range(x):
	(n, m, k) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	if cal(n, m, k, arr):
		print('Yes')
	else:
		print('No')


def test(n, m, a):
	x = [i // m for i in a]
	enough = sum((i for i in x if i >= 2)) >= n
	if n % 2 == 1:
		enough = enough and any((i >= 3 for i in x))
	return enough
T = int(input())
for cc in range(T):
	(n, m, k) = (int(_) for _ in input().split())
	a = [int(_) for _ in input().split()]
	ans = test(n, m, a) or test(m, n, a)
	print('Yes' if ans else 'No')


def solve(n, m):
	b = [x // n for x in a]
	b = list(filter(lambda x: x >= 2, b))
	return sum(b) >= m and (m % 2 == 0 or any((x >= 3 for x in b)))
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print('Yes' if solve(n, m) or solve(m, n) else 'No')


def iin():
	return list(map(int, input().split(' ')))

def solve(n, m, p):
	pigments = p.copy()
	for pigment in pigments:
		cols = pigment // n
		if cols >= m:
			return 'Yes'
		elif cols > 1 and m > 3:
			m = max(2, m - cols)
	return 'No'
[t] = iin()
for _ in range(t):
	[n, m, k] = iin()
	pigments = iin()
	pigments.sort()
	if solve(n, m, pigments) == 'Yes':
		print('Yes')
	else:
		print(solve(m, n, pigments))


import math

def possible_to_color(n, m, colors):
	return try_cover(n, m, colors) or try_cover(m, n, colors)

def try_cover(rows, cols, colors):
	covered = 0
	used_big = False
	for color in colors:
		akt = color // rows
		if akt >= 2:
			covered += akt
		if akt >= 3:
			used_big = True
		if covered == cols or (covered > cols and used_big):
			return True
	return False
tests = int(input())
for _ in range(tests):
	(n, m, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	print('Yes' if possible_to_color(n, m, a) else 'No')


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	valid = 0
	an = a[:]
	ans = 0
	for i in range(len(an)):
		an[i] //= n
		if an[i] >= 2 and ans + 2 <= m:
			ans += 2
			an[i] -= 2
		else:
			an[i] = 0
	if sum(an) + ans >= m:
		valid = 1
	if valid == 0:
		an = a[:]
		ans = 0
		for i in range(len(an)):
			an[i] //= m
			if an[i] >= 2 and ans + 2 <= n:
				ans += 2
				an[i] -= 2
			else:
				an[i] = 0
		if sum(an) + ans >= n:
			valid = 1
	if n == 1 or m == 1:
		valid = 0
	if valid:
		print('Yes')
	else:
		print('No')


def resi():
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mDK = [0] * k
	for i in range(k):
		mDK[i] = a[i] // n
		if mDK[i] == 1:
			mDK[i] = 0
	mDV = [0] * k
	for i in range(k):
		mDV[i] = a[i] // m
		if mDV[i] == 1:
			mDV[i] = 0
	if max(mDV) == 2 and max(mDK) == 2:
		if sum(mDK) >= m and m % 2 == 0:
			print('Yes')
			return
		if sum(mDV) >= n and n % 2 == 0:
			print('Yes')
			return
		print('No')
		return
	if max(mDV) == 2:
		if sum(mDV) >= n and n % 2 == 0:
			print('Yes')
			return
		if sum(mDK) >= m:
			print('Yes')
			return
		print('No')
		return
	if max(mDK) == 2:
		if sum(mDK) >= m and m % 2 == 0:
			print('Yes')
			return
		if sum(mDV) >= n:
			print('Yes')
			return
		print('No')
		return
	if sum(mDK) < m and sum(mDV) < n:
		print('No')
		return
	print('Yes')
for _ in range(int(input())):
	resi()


def rr(a, n, m):
	if m % 2 == 1:
		count = 0
		if a[0] >= 3 * n:
			pass
		else:
			return False
		for i in a:
			if i // n >= 2:
				count += i // n
		if count >= m:
			return True
		else:
			return False
	else:
		count = 0
		for i in a:
			if i // n >= 2:
				count += i // n
		if count >= m:
			return True
		else:
			return False
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a, reverse=True)
	if rr(a, n, m):
		print('Yes')
	elif rr(a, m, n):
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	(m, n, k) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	total = 0
	flag = False
	for num in arr:
		mult = num // n
		if mult > 2:
			flag = True
		if mult >= 2:
			total += mult
	if total >= m and (flag or m % 2 == 0):
		print('Yes')
		continue
	total = 0
	flag = False
	for num in arr:
		mult = num // m
		if mult > 2:
			flag = True
		if mult >= 2:
			total += mult
	if total >= n and (flag or n % 2 == 0):
		print('Yes')
		continue
	print('No')


def solve(a, n, m):
	b = []
	flag = False
	for i in a:
		curr = i // n
		if curr >= 3:
			flag = True
		if curr >= 2:
			b.append(curr)
	if m % 2 == 1:
		if not flag:
			return False
	return sum(b) >= m
for t in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if solve(a.copy(), n, m) or solve(a.copy(), m, n):
		print('Yes')
	else:
		print('No')


def canColor(n, m, colors):
	colors.sort(reverse=True)
	(n, m) = (_n, _m) = sorted([n, m])
	cando = 0
	mfirst = colors[0] // n
	nfirst = colors[0] // m
	for c in colors:
		if c // n > 1:
			if _m == 1:
				if mfirst > 2:
					_m = 0
			else:
				_m -= c // n
		if c // m > 1:
			if _n == 1:
				if nfirst > 2:
					_n = 0
			else:
				_n -= c // m
	if _m <= 0 or _n <= 0:
		cando = 1
	return 'Yes' if cando else 'No'

def main():
	t = int(input())
	for _ in range(t):
		(n, m, k) = map(int, input().split())
		colors = list(map(int, input().split()))
		print(canColor(n, m, colors))
main()


def ss(t, l):
	if sum(l) < t:
		return False
	x = sum(l)
	twos = 0
	odd = 0
	even = 0
	for i in l:
		if i == 2:
			twos += 1
		elif i % 2 == 0:
			even += 1
		else:
			odd += 1
	if t % 2 == 0:
		return True
	xxx = 0
	for i in l:
		if i > 2:
			xxx += 1
	if xxx > 0:
		return True
	return False
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l = sorted(l)[::-1]
	a1 = []
	a2 = []
	for i in l:
		x = i // n
		if x >= 2:
			a1.append(x)
		x = i // m
		if x >= 2:
			a2.append(x)
	if ss(m, a1) or ss(n, a2):
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(cols, rows) = ([], [])
	for count in a:
		if count // n >= 2:
			cols.append(count // n)
		if count // m >= 2:
			rows.append(count // m)
	ans = 'No'
	if m <= sum(cols):
		if m % 2 == 1 and max(cols) == 2:
			pass
		else:
			ans = 'Yes'
	if n <= sum(rows):
		if n % 2 == 1 and max(rows) == 2:
			pass
		else:
			ans = 'Yes'
	print(ans)


t = int(input())
for x in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cols = 0
	for num in a:
		if num // n > 1:
			cols += num // n
	ans = 'No'
	if m % 2 == 0 and cols >= m:
		ans = 'Yes'
	elif cols >= m:
		for num in a:
			if num // n - 1 > 1:
				ans = 'Yes'
	if ans == 'Yes':
		print(ans)
		continue
	rows = 0
	for num in a:
		if num // m > 1:
			rows += num // m
	if n % 2 == 0 and rows >= n:
		ans = 'Yes'
	elif rows >= n:
		for num in a:
			if num // m - 1 > 1:
				ans = 'Yes'
	print(ans)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ok = False
	for _ in range(2):
		(n, m) = (m, n)
		s = 0
		o = 0
		for i in range(k):
			x = a[i] // n
			if x > 1:
				s += x
			if x > 2:
				o += 1
		if s < m:
			continue
		if m % 2 == 0:
			ok = True
			break
		elif o > 0:
			ok = True
			break
	print('Yes' if ok else 'No')


def solve(m, n, arr):
	res = 0
	flag = 0
	for i in arr:
		if i // n <= 1:
			continue
		res += i // n
		if i // n >= 3:
			flag = 1
	if res >= m and (m % 2 == 1 and flag or m % 2 == 0):
		return 1
	else:
		return 0
t = int(input())
while t:
	(n, m, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	if solve(m, n, arr) or solve(n, m, arr):
		print('Yes')
	else:
		print('No')
	t -= 1


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	l.sort(reverse=True)
	i = 0
	ans = 0
	flag = False
	while i < k:
		x = l[i] // m
		if x > 2:
			flag = True
		if x >= 2:
			ans += x
		i += 1
	if ans >= n and (flag or n % 2 == 0):
		print('Yes')
	else:
		i = 0
		ans = 0
		False
		while i < k:
			x = l[i] // n
			if x > 2:
				flag = True
			if x >= 2:
				ans += x
			i += 1
		if ans >= m and (flag or m % 2 == 0):
			print('Yes')
		else:
			print('No')


for i in range(int(input())):
	(n, m, k) = [int(x) for x in input().split()]
	colors = [int(x) for x in input().split()]
	(col, row) = ([], [])
	for i in range(k):
		cell = colors[i]
		if cell // n >= 2:
			col.append(cell // n)
		else:
			col.append(0)
		if cell // m >= 2:
			row.append(cell // m)
		else:
			row.append(0)
	ans1 = False
	if sum(col) >= m:
		if m % 2 == 1:
			for i in col:
				if i >= 3:
					ans1 = True
					break
		else:
			ans1 = True
	ans2 = False
	if sum(row) >= n:
		if n % 2 == 1:
			for i in row:
				if i >= 3:
					ans2 = True
					break
		else:
			ans2 = True
	fin = 'Yes' if ans1 or ans2 else 'No'
	print(fin)


def main():
	for t in range(int(input())):
		(n, m, k) = map(int, input().split())
		a = sorted(list(map(int, input().split())), reverse=True)
		(x, y) = (0, 0)
		(flag1, flag2) = (False, False)
		for i in range(k):
			if a[i] // n > 2:
				flag1 = True
			if a[i] // n >= 2:
				x += a[i] // n
		for i in range(k):
			if a[i] // m > 2:
				flag2 = True
			if a[i] // m >= 2:
				y += a[i] // m
		if x >= m and (m % 2 == 0 or (m % 2 == 1 and flag1)) or (y >= n and (n % 2 == 0 or (n % 2 == 1 and flag2))):
			print('Yes')
		else:
			print('No')
main()


for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	color = list(map(int, input().split()))
	row_cost = m
	col_cost = n
	tot = 0
	flag = False
	for i in color:
		if i // row_cost > 2:
			flag = True
		if i // row_cost >= 2:
			tot += i // row_cost
	if tot >= n and (n % 2 == 0 or flag):
		print('Yes')
		continue
	tot = 0
	flag = False
	for i in color:
		if i // col_cost > 2:
			flag = True
		if i // col_cost >= 2:
			tot += i // col_cost
	if tot >= m and (m % 2 == 0 or flag):
		print('Yes')
	else:
		print('No')


def column(a, n, m, k):
	sumi = 0
	if n % 2:
		if a[-1] >= 3 * m:
			a[-1] -= 3 * m
			n -= 3
			sumi += a[-1] // m
			a[-1] = 0
		else:
			return -1
	r = 2 * m
	for i in range(k):
		if a[i] >= r:
			sumi += a[i] // m
	if sumi >= n:
		return 1
	else:
		return -1
t = int(input())
while t > 0:
	x = input().split()
	(n, m, k) = (int(x[0]), int(x[1]), int(x[2]))
	a = input().split()
	for i in range(k):
		a[i] = int(a[i])
	fl = 0
	a.sort()
	p = n
	q = m
	b = [a[i] for i in range(k)]
	c = column(b, p, q, k)
	d = column(a, m, n, k)
	if c == 1 or d == 1:
		print('Yes')
	else:
		print('No')
	t -= 1


t = int(input())
while t > 0:
	t -= 1
	(n, m, k) = [int(x) for x in input().split(' ')]
	quantities = [int(x) for x in input().split(' ')]
	row_count = 0
	flag = False
	for num in quantities:
		if num // m >= 2:
			row_count += num // m
		if num // m >= 3:
			flag = True
	if row_count >= n and (n % 2 == 0 or flag):
		print('Yes')
		continue
	col_count = 0
	flag = False
	for num in quantities:
		if num // n >= 2:
			col_count += num // n
		if num // n >= 3:
			flag = True
	if col_count >= m and (m % 2 == 0 or flag):
		print('Yes')
	else:
		print('No')


t = int(input())
while t > 0:
	t -= 1
	(n, m, k) = map(int, input().split())
	(numH, numV) = (0, 0)
	(ntH, ntV) = (False, False)
	a = list(map(int, input().split()))
	for i in a:
		if int(i / n) > 1:
			numH += int(i / n)
			if int(i / n) > 2:
				ntH = True
		if int(i / m) > 1:
			numV += int(i / m)
			if int(i / m) > 2:
				ntV = True
	ans = False
	if numH >= m:
		if m % 2 == 0 or ntH:
			ans = True
	if numV >= n:
		if n % 2 == 0 or ntV:
			ans = True
	if ans:
		print('Yes')
	else:
		print('No')


import math as mt
from collections import defaultdict, deque
from bisect import bisect_left as b_l
from bisect import bisect_right as b_r
import sys
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == 1 or m == 1:
		print('No')
		continue
	else:
		a.sort(reverse=True)
		total = m
		if total & 1:
			flag = False
		else:
			flag = True
		for i in a:
			if total & 1:
				if i // n >= 3:
					flag = True
			if i // n > 1:
				total -= i // n
		if total <= 0 and flag:
			print('Yes')
			continue
		total = n
		if total & 1:
			flag = False
		else:
			flag = True
		for i in a:
			if total & 1:
				if i // m >= 3:
					flag = True
			if i // m > 1:
				total -= i // m
		if total <= 0 and flag:
			print('Yes')
			continue
		print('No')


for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	m1 = []
	n1 = []
	m01 = 0
	n01 = 0
	for j in map(int, input().split()):
		m1 += [j // n]
		n1 += [j // m]
		if j // n > 1:
			m01 += j // n
		if j // m > 1:
			n01 += j // m
	maxm1 = max(m1)
	maxn1 = max(n1)
	summ1 = sum(m1)
	sumn1 = sum(n1)
	if m == 1 and summ1 > 0 or (n == 1 and sumn1 > 0) or (m01 >= m and (maxm1 > 2 or m % 2 < 1)) or (n01 >= n and (maxn1 > 2 or n % 2 < 1)):
		print('Yes')
	else:
		print('No')


from collections import Counter
from functools import *
from sys import setrecursionlimit, getsizeof
setrecursionlimit(100050)

def f(n, m, a):
	temp = [i // n for i in a if i // n > 1]
	temp.sort(reverse=True)
	cnt = 0
	while cnt < len(temp) and temp[cnt] > 2:
		cnt += 1
	(s, p) = (0, 0)
	while p < len(temp) and s + temp[p] < m:
		s += temp[p]
		p += 1
	rem = m - s
	if p == len(temp):
		return False
	if rem == 1:
		return cnt >= 1
	return True
x = int(input())
while x:
	x -= 1
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if f(n, m, a) or f(m, n, a):
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr1 = []
	arr2 = []
	for i in arr:
		if i // n > 1:
			arr1.append(i // n)
		if i // m > 1:
			arr2.append(i // m)
	arr1.sort(reverse=True)
	arr2.sort(reverse=True)
	s1 = 0
	for i in arr1:
		s1 += i
		if s1 > m:
			if i - (s1 - m) == 1 and arr1[0] == 2:
				break
			s1 = m
		if s1 == m:
			break
	s2 = 0
	for i in arr2:
		s2 += i
		if s2 > n:
			if i - (s2 - n) == 1 and arr2[0] == 2:
				break
			s2 = n
		if s2 == n:
			break
	if s1 == m or s2 == n:
		print('Yes')
	else:
		print('No')


def solve(n, m, k, K):
	Q = [x for x in K]
	P = [0 for x in K]
	idx = 0
	z = n
	for i in range(k):
		if Q[i] >= 2 * m and z >= 2:
			Q[i] -= 2 * m
			P[i] = 2
			z -= 2
	if z == 0:
		return True
	for i in range(k):
		if P[i] > 0:
			z -= Q[i] // m
	if z <= 0:
		return True
	return False

def read():
	s = input().split(' ')
	n = int(s[0])
	m = int(s[1])
	k = int(s[2])
	s = input().split(' ')
	return (n, m, k, sorted([int(x) for x in s], reverse=True))

def main():
	n = int(input())
	for _ in range(n):
		(n, m, k, K) = read()
		if solve(n, m, k, K) or solve(m, n, k, K):
			print('Yes')
		else:
			print('No')
		pass
	pass
main()


try:
	for _ in range(int(input())):
		(n, m, k) = map(int, input().split(' '))
		l = list(map(int, input().split(' ')))
		l.sort()
		mul = m * n
		mn = 10000000
		f = 0
		mx = 0
		g = 0
		for i in range(k):
			if l[i] // n > 1 and f == 0:
				mul = mul - (l[i] - l[i] % n)
				mn = min(mn, l[i] - l[i] % n)
				if mul == n:
					f = 1
			else:
				mx = max(mx, l[i])
		if f == 1:
			if mn // n < mx // n:
				print('Yes')
			else:
				g = 1
		elif mul <= 0:
			print('Yes')
		else:
			g = 1
		if g == 1:
			mul = m * n
			mn = 10000000
			f = 0
			mx = 0
			for i in range(k):
				if l[i] // m > 1 and f == 0:
					mul = mul - (l[i] - l[i] % m)
					mn = min(mn, l[i] - l[i] % m)
					if mul == m:
						f = 1
				else:
					mx = max(mx, l[i])
			if f == 1:
				if mn // m < mx // m:
					print('Yes')
				else:
					print('No')
			elif mul <= 0:
				print('Yes')
			else:
				print('No')
except:
	pass