Cirno_9baka has a paper tape with $n$ cells in a row on it. As he thinks that the blank paper tape is too dull, he wants to paint these cells with $m$ kinds of colors. For some aesthetic reasons, he thinks that the $i$-th color must be used exactly $a_i$ times, and for every $k$ consecutive cells, their colors have to be distinct.

Help Cirno_9baka to figure out if there is such a way to paint the cells.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10000$)  — the number of test cases. The description of test cases follows.

The first line of each test case contains three integers $n$, $m$, $k$ ($1 \leq k \leq n \leq 10^9$, $1 \leq m \leq 10^5$, $m \leq n$). Here $n$ denotes the number of cells, $m$ denotes the number of colors, and $k$ means that for every $k$ consecutive cells, their colors have to be distinct.

The second line of each test case contains $m$ integers $a_1, a_2, \cdots , a_m$ ($1 \leq a_i \leq n$)  — the numbers of times that colors have to be used. It's guaranteed that $a_1 + a_2 + \ldots + a_m = n$.

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


-----Output-----

For each test case, output "YES" if there is at least one possible coloring scheme; otherwise, output "NO".

You may print each letter in any case (for example, "YES", "Yes", "yes", and "yEs" will all be recognized as positive answers).


-----Examples-----

Input
2
12 6 2
1 1 1 1 1 7
12 6 2
2 2 2 2 2 2
Output
NO
YES


-----Note-----

In the first test case, there is no way to color the cells satisfying all the conditions.

In the second test case, we can color the cells as follows: $(1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6)$. For any $2$ consecutive cells, their colors are distinct.

Source: codeforces | Difficulty: MEDIUM
Tags: Greedy algorithms

Mathematics

Constructive algorithms


Solutions:
import sys
import math

def input_parse_expression(input_lines, i):
	(n, m, k) = map(int, input_lines[2 * i + 1].split())
	a = map(int, input_lines[2 * i + 2].split())
	return (n, m, k, a)

def solve(test_case_input):
	(n, m, k, a) = test_case_input
	if m < k:
		return 'NO'
	max_a_allowed = n // k
	num_1_gt_allowed = n % k
	for ai in a:
		if ai - max_a_allowed > 1:
			return 'NO'
		if ai - max_a_allowed == 1:
			num_1_gt_allowed -= 1
		if num_1_gt_allowed < 0:
			return 'NO'
	return 'YES'

def main():
	input_str = sys.stdin.read()
	input_lines = input_str.strip().split('\n')
	n_cases = int(input_lines[0])
	for i in range(n_cases):
		test_case_input = input_parse_expression(input_lines, i)
		solution = solve(test_case_input)
		print(solution)
main()


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, m, k) = map(int, sys.stdin.readline().split())
	lst = list(map(int, sys.stdin.readline().split()))
	ma = max(lst)
	if n % k == 0:
		ele = n // k
		ct = lst.count(ele)
		if ma > ele or ct > k:
			print('NO')
		else:
			print('YES')
	else:
		ele = n // k + 1
		ct = lst.count(ele)
		if ma > ele or ct > n % k:
			print('NO')
		else:
			print('YES')


import sys

def solve():
	inp = sys.stdin.readline
	(n, m, k) = map(int, inp().split())
	a = list(map(int, inp().split()))
	d = n // k
	r = n % k
	b = k - r
	c = r
	a.sort(reverse=True)
	for v in a:
		if v > d + 1:
			print('NO')
			return
		if v == d + 1:
			if c == 0:
				print('NO')
				return
			c -= 1
	print('YES')

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


import sys
input = sys.stdin.readline

def solve():
	(N, M, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	D = N // K
	R = N % K
	for i in A:
		if i > D + 1:
			print('NO')
			return
		elif i == D + 1:
			R -= 1
	if R < 0:
		print('NO')
	else:
		print('YES')
for _ in range(int(input())):
	solve()


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s.strip())

def invr():
	return map(int, input().split())
for _ in range(inp()):
	(n, m, k) = invr()
	arr = inlt()
	arr.sort(reverse=True)
	val = n // k
	c = 0
	for i in arr:
		if i > val + 1:
			c = -1
			break
		elif i == val + 1:
			c += 1
		else:
			break
	if c == -1:
		print('NO')
	elif c <= n % k:
		print('YES')
	else:
		print('NO')


from sys import stdin

def main():
	for _ in range(int(stdin.readline().strip())):
		(n, m, k) = list(map(int, stdin.readline().strip().split()))
		colors = list(map(int, stdin.readline().strip().split()))
		colors.sort()
		x = n // k + (n % k != 0)
		if max(colors) > x:
			print('NO')
		else:
			count = 0
			for i in colors:
				if i == x:
					count += 1
			if count > n % k and n % k != 0:
				print('NO')
			else:
				print('YES')
main()


import sys
input = sys.stdin.readline

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

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	(n, m, k) = readInts()
	arr = readList()
	(val, r) = (n // k, n % k)
	cnt = 0
	for i in range(m):
		if arr[i] <= val:
			continue
		if arr[i] > val + 1:
			return 'NO'
		cnt += 1
	return 'YES' if cnt <= r else 'NO'
for _ in range(int(input())):
	print(solve())


import sys
import math

def fn(n, m, k, colors):
	max_value = max(colors)
	cap = math.ceil(n / k)
	rem = n % k
	count = 0
	if max_value > cap:
		return 'NO'
	elif max_value < cap:
		return 'YES'
	if rem == 0:
		return 'YES'
	for item in colors:
		if item == cap:
			count += 1
			if count > rem:
				return 'NO'
	return 'YES'
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	(n, m, k) = tuple([int(x) for x in input[2 * i + 1].strip('\n').split(' ')])
	colors = [int(x) for x in input[2 * i + 2].strip('\n').split(' ')]
	print(fn(n, m, k, colors))


n = int(input())
out = []
for i in range(0, n):
	t = list(map(int, input().split()))
	data = list(map(int, input().split()))
	w = data.sort()
	o = True
	j = t[1] - 1
	d = t[0] % t[2]
	r = t[0] // t[2]
	while True:
		if data[j] > r:
			if d > 0 and data[j] - 1 == r:
				d = d - 1
				j = j - 1
			else:
				o = False
				break
		if data[j] <= r:
			break
	if o:
		out.append('YES')
	else:
		out.append('NO')
for i in range(0, n):
	print(out[i])


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	key = 0
	div = n // k
	temp = n % k
	c = 0
	for j in arr:
		if j == div + 1:
			c += 1
		elif j > div + 1:
			key = 1
			break
	if c > temp:
		key = 1
	if key == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	lst = list(map(int, input().split()))
	lst1 = list(map(int, input().split()))
	(n, m, k) = (lst[0], lst[1], lst[2])
	maxf = 0
	maxe = 0
	if n % k:
		maxf = n // k + 1
		maxe = n % k
	else:
		maxf = n // k
		maxe = k
	for val in lst1:
		if val > maxf:
			maxe = -1
			break
		elif val == maxf:
			maxe -= 1
	if maxe < 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, m, k) = [int(i) for i in input().strip().split()]
	a = [int(i) for i in input().strip().split()]
	if k == 1:
		print('YES')
	elif k > m:
		print('NO')
	else:
		tot = n // k
		val = n % k
		check = True
		for i in range(m):
			if a[i] > tot:
				if a[i] == tot + 1 and val:
					val -= 1
				else:
					check = False
					break
			else:
				pass
		if check:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	size = n // k
	extra = n % k
	flag = True
	arr = list(map(int, input().split()))
	for x in arr:
		if x > size:
			if x - size == 1:
				if extra <= 0:
					flag = False
				else:
					extra -= 1
			else:
				flag = False
	if flag:
		print('YES')
	else:
		print('NO')


a = int(input())
for _ in range(a):
	c = list(map(int, input().split()))
	d = list(map(int, input().split()))
	s = 1
	if c[2] > c[1]:
		print('NO')
	elif c[0] % c[2] == 0:
		if max(d) > c[0] // c[2]:
			print('NO')
		else:
			print('YES')
	elif max(d) > c[0] // c[2] + 1:
		print('NO')
	elif max(d) == c[0] // c[2] + 1:
		if d.count(max(d)) > c[0] % c[2]:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m, k) = tuple(map(int, input().split()))
	arr = list(map(int, input().split()))
	(q, r) = (n // k, n % k)
	res = True
	for c in arr:
		if c > q + 1:
			res = False
			break
		elif c == q + 1:
			if r > 0:
				r -= 1
			else:
				res = False
				break
	print('YES' if res else 'NO')


t = int(input())
for k in range(t):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if n % k == 0:
		p = int(n / k)
	else:
		p = int(n / k) + 1
	if n % k == 0:
		if max(l) > p:
			print('NO')
		else:
			print('YES')
	else:
		c = 0
		if max(l) > p:
			print('NO')
		else:
			for i in range(m):
				if l[i] == p:
					c += 1
				if c > n % k:
					print('NO')
					break
			if c <= n % k:
				print('YES')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	d = n // k
	r = n % k
	f = 'YES'
	for i in l:
		if i > d + 1:
			f = 'NO'
			break
		elif i == d + 1:
			r -= 1
			if r < 0:
				f = 'NO'
				break
	print(f)


for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	z = max(arr)
	if (z - 1) * k + arr.count(z) > n:
		ans = 'NO'
	else:
		ans = 'YES'
	print(ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if m < k:
		print('NO')
	else:
		l.sort()
		for i in range(n % k):
			l[m - i - 1] -= 1
		l.sort()
		if n // k < l[m - 1]:
			print('NO')
		else:
			print('YES')


def main():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split())
		a = list(map(int, input().split()))
		max_occ = (n + k - 1) // k
		count_max_occ = 0
		possible = True
		for j in range(m):
			if a[j] > max_occ:
				possible = False
				break
			if a[j] == max_occ:
				count_max_occ += 1
		n_k = n % k
		if n_k == 0:
			n_k = k
		if count_max_occ > n_k:
			possible = False
		if possible:
			print('YES')
		else:
			print('NO')
main()


def ceildiv(a, b):
	return -(a // -b)
for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if k > m:
		print('NO')
		continue
	a = sorted(a, reverse=True)
	okay = True
	max_idx = min(n % k, len(a))
	for i in range(max_idx):
		if a[i] > n // k + 1:
			okay = False
	for i in range(max_idx, len(a)):
		if a[i] > n // k:
			okay = False
	if okay:
		print('YES')
	else:
		print('NO')


t = int(input())
i = 0
while i < t:
	n_m_k = [int(b) for b in input().split()]
	frequency = [int(c) for c in input().split()]
	a_i = max(frequency)
	n_a_i = frequency.count(max(frequency))
	n = n_m_k[0]
	k = n_m_k[2]
	if n_m_k[2] == 1:
		print('YES')
	elif n == n_m_k[2]:
		if a_i == 1:
			print('YES')
		else:
			print('NO')
	elif n % k == 0:
		if a_i == n / k:
			if n_a_i <= k:
				print('YES')
			else:
				print('NO')
		elif a_i < n / k:
			print('YES')
		else:
			print('NO')
	elif a_i == n // k + 1:
		if n_a_i <= n % k:
			print('YES')
		else:
			print('NO')
	elif a_i < n // k + 1:
		print('YES')
	else:
		print('NO')
	i += 1


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split(' '))
	vals = list(map(int, input().split(' ')))
	res = 'YES'
	for v in vals:
		if not n % k and v > n / k:
			res = 'NO'
			break
		if n % k and v > n // k + 1:
			res = 'NO'
			break
		if n % k and v == n // k + 1:
			res = 'YES'
			if vals.count(v) > n % k:
				res = 'NO'
	print(res)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(x, y) = divmod(n, k)
	if max(a) > x + 1 or a.count(x + 1) > y:
		print('NO')
	else:
		print('YES')


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

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

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n, m, k) = inp_arr()
	a = inp_arr()
	rem = n % k
	maxx = n // k
	maxx2 = maxx + 1
	for x in a:
		if x > maxx2:
			print('NO')
			return
		if x == maxx2 and rem <= 0:
			print('NO')
			return
		if x == maxx2:
			rem -= 1
	print('YES')
(tt,) = inp_arr()
for t in range(tt):
	solve()


t = int(input())
for i in range(t):
	s = list(map(int, input().split()))
	x = list(map(int, input().split()))
	if s[0] % s[2] == 0:
		a = 0
	else:
		a = 1
	b = a + s[0] // s[2]
	count = 0
	for j in x:
		if j > b:
			print('NO')
			break
		if j == b:
			count += 1
	else:
		if s[0] % s[2] == 0:
			print('YES')
		elif count > s[0] % s[2]:
			print('NO')
		else:
			print('YES')


t = int(input())
for _ in range(t):
	(n, m, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	ost = n % k
	ost_s = set()
	d = n // k
	for i in a:
		if i > d:
			if ost <= 0 or i - d > 1:
				print('NO')
				break
			else:
				ost -= 1
	else:
		print('YES')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	if n % k == 0:
		if a[0] > n // k:
			print('NO')
		else:
			print('YES')
	elif a[0] > n // k + 1 or a.count(n // k + 1) > n % k:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if (max(arr) - 1) * k + arr.count(max(arr)) > n:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, m, k) = list(map(int, input().split(sep=' ')))
	a = list(map(int, input().split(sep=' ')))
	m = max(a)
	x = n // k
	count = a.count(m)
	if n >= (m - 1) * k + count:
		print('YES')
	else:
		print('NO')


import math
m = int(input())
for i in range(m):
	(c, m, k) = input().split()
	c = int(c)
	k = int(k)
	nums = [int(a) for a in input().split()]
	e = math.ceil(c / k)
	r = c % k if c % k != 0 else k
	b = 0
	for i in nums:
		if i == e:
			b += 1
		if i > e:
			b = -1
			break
	if b == -1:
		print('NO')
	elif b <= r:
		print('YES')
	else:
		print('NO')


t = int(input())
for t_ in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	pos = True
	c = min(n - n // k * k, m)
	for i in range(c):
		pos &= a[i] <= (n + k - 1) // k
	for i in range(c, m):
		pos &= a[i] <= n // k
	if pos:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, m, k) = list(map(int, input().split(sep=' ')))
	a = list(map(int, input().split(sep=' ')))
	m = max(a)
	z = n // k
	cnt = a.count(m)
	if n < (m - 1) * k + cnt:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(0, t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n % k == 0:
		max_f = n // k
		max_e = k
	else:
		max_f = n // k + 1
		max_e = n % k
	for i in range(0, m):
		if a[i] > max_f:
			max_e = -1
			break
		elif a[i] == max_f:
			max_e = max_e - 1
	if max_e < 0:
		print('NO')
	else:
		print('YES')


test = int(input())
while test:
	(n, m, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	max_f = max_o = 0
	found = 1
	if n % k:
		max_f = n // k + 1
		max_o = n % k
	else:
		max_f = n // k
		max_o = k
	for i in a:
		if i > max_f:
			found = 0
			break
		elif i == max_f:
			max_o -= 1
		if max_o < 0:
			found = 0
			break
	if found:
		print('YES')
	else:
		print('NO')
	test -= 1


import math
from collections import Counter

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

def nt():
	return int(input())

def st():
	return input()
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def prefix(L):
	size = len(L)
	for i in range(1, size):
		L[i] = L[i] + L[i - 1]
	return L
for _ in range(int(input())):
	(n, m, k) = li()
	L = li()
	m = max(L)
	fre = L.count(m)
	if m > math.ceil(n / k):
		print(no)
	elif m == math.ceil(n / k) and fre <= (n - 1) % k + 1:
		print(yes)
	elif m < math.ceil(n / k):
		print(yes)
	else:
		print(no)


import sys, os
if os.getlogin() == 'arun':
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
from collections import defaultdict
import math
import heapq
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	lt = list(map(int, input().split()))
	count = 0
	valid = n % k if n % k else k
	seg = math.ceil(n / k)
	if m < k:
		print('NO')
		continue
	for x in lt:
		if x == seg:
			count += 1
		if x > seg or valid < count:
			count = valid + 1
	print('NO' if count > valid else 'YES')


def fun(n, k, m, l):
	r = n % k
	for i in range(m):
		if l[i] > n // k:
			if l[i] - n // k > 1:
				return -1
			else:
				r = r - 1
			if r < 0:
				return -1
	return 0
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if fun(n, k, m, l) == -1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	l = list(map(int, input().strip().split()))
	m = list(map(int, input().strip().split()))
	flag = False
	d = 0
	p = l[0] // l[2]
	if l[0] % l[2] == 0:
		for i in range(0, len(m)):
			if m[i] > p:
				d = 1
				break
	else:
		c = l[0] % l[2]
		for i in range(0, len(m)):
			if m[i] == p + 1:
				c -= 1
			elif m[i] > p + 1:
				d = 1
				break
			if c < 0:
				d = 1
				break
	if d == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	res = n % k
	answer = 'YES'
	a = list(map(int, input().split()))
	for i in range(0, m):
		if a[i] > n // k + 1:
			answer = 'NO'
		if a[i] == n // k + 1:
			res -= 1
	if res < 0:
		answer = 'NO'
	print(answer)


from collections import defaultdict

def check(n, m, k, aa):
	aa.sort()
	max_count = aa[-1]
	if max_count <= 1:
		return True
	n_max_count = sum([a == max_count for a in aa])
	if (n - (n_max_count - 1) + k - 1) // k < max_count:
		return False
	return True
n = int(input())
for test_n in range(n):
	(n, m, k) = map(int, input().split(' '))
	aa = list(map(int, input().split(' ')))
	assert len(aa) == m
	assert sum(aa) == n
	is_valid = check(n, m, k, aa)
	print('YES' if is_valid else 'NO')


t = int(input())
for tc in range(t):
	(n, m, k) = input().split()
	(n, m, k) = (int(n), int(m), int(k))
	c = input().split()
	colors = []
	for i in range(m):
		colors.append(int(c[i]))
	rem = n % k
	cnt = 0
	flag = True
	mx = n // k if n % k == 0 else n // k + 1
	for i in range(m):
		if colors[i] > mx:
			flag = False
			break
		if colors[i] == mx:
			cnt += 1
	if flag == False:
		print('NO')
		continue
	if n % k == 0:
		print('YES')
	elif cnt <= rem:
		print('YES')
	else:
		print('NO')


testcases = int(input())
for a in range(testcases):
	possible = True
	nmk = input()
	colors = input()
	nmk = nmk.split()
	n = int(nmk[0])
	m = int(nmk[1])
	k = int(nmk[2])
	colors = colors.split()
	colors = [int(a) for a in colors]
	if max(colors) >= n // k + (n % k > 0):
		if max(colors) > n // k + (n % k > 0):
			possible = False
		elif max(colors) == n // k + (n % k > 0):
			if colors.count(max(colors)) > n % k > 0:
				possible = False
	print('YES' if possible else 'NO')


for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	freq = list(map(int, input().split()))
	max_col = max(freq)
	rem = n // k
	count = freq.count(max_col)
	if n >= (max_col - 1) * k + count:
		print('YES')
	else:
		print('NO')


def solve(N, M, K, arr):
	arr.sort(reverse=True)
	_max = arr[0]
	i = 0
	while i < M and arr[i] == _max:
		i += 1
	left = N - _max * i
	need = (_max - 1) * (K - i)
	if need > left:
		return 'NO'
	else:
		return 'YES'
T = int(input().strip())
for _ in range(T):
	(N, M, K) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = solve(N, M, K, arr)
	print(ans)


import heapq
import math
t = int(input())
while t:
	(n, m, k) = input().split()
	n = int(n)
	m = int(m)
	k = int(k)
	heap = input().split()
	good = True
	heap = [int(ele) for ele in heap]
	count = 0
	lastSegment = n % k if n % k != 0 else k
	for num in heap:
		if num == math.ceil(n / k):
			count += 1
		if num > math.ceil(n / k):
			good = False
			break
	if good and count <= lastSegment:
		print('YES')
	else:
		print('NO')
	t -= 1


def ceiling(a, b):
	if a % b == 0:
		return a // b
	else:
		return a // b + 1

def max_pos(n, k):
	if n % k == 0:
		return k
	else:
		return n % k
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = max(a)
	co = a.count(b)
	if b > ceiling(n, k):
		print('NO')
	elif b == ceiling(n, k):
		if co > max_pos(n, k):
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


from math import ceil
t = int(input())
for _ in range(t):
	(n, m, k) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	if any([a_i > ceil(n / k) for a_i in a]) or m < k:
		print('NO')
		continue
	elif sum([a_i == ceil(n / k) for a_i in a]) <= n % k or n % k == 0:
		print('YES')
		continue
	else:
		print('NO')
		continue


import math
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	L = list(map(int, input().split()))
	count = 0
	t = 0
	for i in range(m):
		if L[i] > math.ceil(n / k):
			print('NO')
			t = 1
			break
		elif L[i] == math.ceil(n / k) and L[i] != n // k:
			count += 1
	if t != 1:
		if count <= n % k:
			print('YES')
		else:
			print('NO')


def f(P, k, n, m):
	S = []
	net = 0
	p = n // k
	c = n % k
	L = sorted(P, reverse=True)
	for i in range(m):
		if L[i] > p:
			net += p
			L[i] -= p
		else:
			net += L[i]
			L[i] = 0
		if L[i] > 0:
			if c > 0:
				c -= 1
				L[i] -= 1
				net += 1
	if net == n:
		return 'YES'
	else:
		return 'NO'
x = int(input())
for i in range(x):
	(n, m, k) = map(int, input().split())
	L = list(map(int, input().split()))
	print(f(L, k, n, m))


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)[::-1]
	res = 'YES'
	if k > m:
		res = 'NO'
	full = n // k
	rem = n % k
	for i in range(m):
		cur = a[i]
		have_space = full + (rem > i)
		if cur > have_space:
			res = 'NO'
	print(res)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	fl = 0
	for i in range(m):
		if a[i] == (n + k - 1) // k:
			fl += 1
		if a[i] > (n + k - 1) // k:
			fl = 1 << 30
	print('YES' if fl <= (n - 1) % k + 1 else 'NO')


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	(*a,) = map(int, input().split())
	f = 0
	for a_i in a:
		if a_i == (n + k - 1) // k:
			f += 1
		elif a_i > (n + k - 1) // k:
			f = 1e+30
	if f <= (n - 1) % k + 1:
		print('YES')
	else:
		print('NO')


R = lambda : [*map(int, input().split())]
exec(R()[0] * "n,m,k=R();a=R();print('YNEOS'[a.count(m:=max(a))+k*m-k>n::2]);")