Let's denote the median of a sequence $s$ with odd length as the value in the middle of $s$ if we sort $s$ in non-decreasing order. For example, let $s = [1, 2, 5, 7, 2, 3, 12]$. After sorting, we get sequence $[1, 2, 2, \underline{3}, 5, 7, 12]$, and the median is equal to $3$.

You have a sequence of $n$ integers $[1, 2, \dots, n]$ and an odd integer $k$.

In one step, you choose any $k$ elements from the sequence and erase all chosen elements except their median. These elements do not have to go continuously (gaps are allowed between them).

For example, if you have a sequence $[1, 2, 3, 4, 5, 6, 7]$ (i.e. $n=7$) and $k = 3$, then the following options for the first step are possible:

choose $[1, \underline{2}, 3]$; $2$ is their median, so it is not erased, and the resulting sequence is $[2, 4, 5, 6, 7]$;

choose $[2, \underline{4}, 6]$; $4$ is their median, so it is not erased, and the resulting sequence is $[1, 3, 4, 5, 7]$;

choose $[1, \underline{6}, 7]$; $6$ is their median, so it is not erased, and the resulting sequence is $[2, 3, 4, 5, 6]$;

and several others.

You can do zero or more steps. Can you get a sequence $b_1$, $b_2$, ..., $b_m$ after several steps?

You'll be given $t$ test cases. Solve each test case independently.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains three integers $n$, $k$, and $m$ ($3 \le n \le 2 \cdot 10^5$; $3 \le k \le n$; $k$ is odd; $1 \le m < n$) — the length of the sequence you have, the number of elements you choose in each step and the length of the sequence you'd like to get.

The second line of each test case contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_1 < b_2 < \dots < b_m \le n$) — the sequence you'd like to get, given in the ascending order.

It's guaranteed that the total sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print YES if you can obtain the sequence $b$ or NO otherwise. You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).


-----Examples-----

Input
4
3 3 1
1
7 3 3
1 5 7
10 5 3
4 5 6
13 7 7
1 3 5 7 9 11 12
Output
NO
YES
NO
YES


-----Note-----

In the first test case, you have sequence $[1, 2, 3]$. Since $k = 3$ you have only one way to choose $k$ elements — it's to choose all elements $[1, \underline{2}, 3]$ with median $2$. That's why after erasing all chosen elements except its median you'll get sequence $[2]$. In other words, there is no way to get sequence $b = [1]$ as the result.

In the second test case, you have sequence $[1, 2, 3, 4, 5, 6, 7]$ and one of the optimal strategies is following:

choose $k = 3$ elements $[2, \underline{3}, 4]$ and erase them except its median; you'll get sequence $[1, 3, 5, 6, 7]$;

choose $3$ elements $[3, \underline{5}, 6]$ and erase them except its median; you'll get desired sequence $[1, 5, 7]$;

In the fourth test case, you have sequence $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]$. You can choose $k=7$ elements $[2, 4, 6, \underline{7}, 8, 10, 13]$ and erase them except its median to get sequence $b$.

Source: codeforces | Difficulty: HARD
Tags: Greedy algorithms

Mathematics

Constructive algorithms


Solutions:
import heapq
t = int(input())
for _ in range(t):
	(n, k, m) = map(int, input().split())
	l = [0] + list(map(int, input().split())) + [n + 1]
	diffs = [l[i + 1] - l[i] - 1 for i in range(m + 1)]
	if sum(diffs) % (k - 1) > 0:
		print('NO')
		continue
	ls = 0
	ind = -1
	while ls < k // 2:
		ind += 1
		ls += diffs[ind]
	rs = 0
	ind2 = m + 1
	while rs < k // 2:
		ind2 -= 1
		rs += diffs[ind2]
	if ind2 <= ind:
		print('NO')
	else:
		print('YES')


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	L = [int(x) for x in stdin.readline().split(' ')]
	(n, k, m) = (L[0], L[1], L[2])
	A = [int(x) for x in stdin.readline().split(' ')]
	if (n - m) % (k - 1) != 0:
		print('NO')
		continue
	works = False
	k = (k - 1) // 2
	count = 0
	for i in range(m):
		a = A[i]
		if a - i - 1 >= k and n - a - (m - 1 - i) >= k:
			works = True
			break
	if works:
		print('YES')
	else:
		print('NO')


from sys import stdin
tt = int(stdin.readline())
for loop in range(tt):
	(n, k, m) = map(int, stdin.readline().split())
	b = list(map(int, stdin.readline().split()))
	if (n - m) % (k - 1) != 0:
		print('NO')
		continue
	lis = [1] * n
	for i in b:
		lis[i - 1] = 0
	ns = 0
	while ns != k // 2:
		ns += lis[-1]
		del lis[-1]
	ns = 0
	lis.reverse()
	while ns != k // 2:
		ns += lis[-1]
		del lis[-1]
	if len(lis) == sum(lis):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, k, m) = tuple(map(int, input().split(' ')))
	ml = set(map(int, input().split(' ')))
	havitada = []
	for i in range(1, n + 1):
		if i not in ml:
			havitada.append(i)
	saab = False
	if len(havitada) % (k - 1) != 0:
		print('no')
		continue
	for i in range(k // 2 - 1, len(havitada) - k // 2):
		if havitada[i + 1] - havitada[i] != 1:
			print('yes')
			break
	else:
		print('no')


for _ in range(int(input())):
	(n, k, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	remain = [0] * (n + 1)
	for x in arr:
		remain[x] = 1
	use = n - m
	if use % (k - 1) != 0:
		print('NO')
	else:
		flg = False
		cnt = 0
		for x in range(1, n + 1):
			if remain[x] == 1:
				if cnt >= k // 2 and use - cnt >= k // 2:
					flg = True
			else:
				cnt += 1
		if flg == True:
			print('YES')
		else:
			print('NO')


from sys import stdin, stdout
from collections import defaultdict
import math

def main():
	t = int(stdin.readline())
	for _ in range(t):
		(n, k, m) = list(map(int, stdin.readline().split()))
		arr = list(map(int, stdin.readline().split()))
		if (n - m) % (k - 1) != 0:
			stdout.write('NO\n')
			continue
		is_can = False
		for (i, a) in enumerate(arr):
			left = a - (i + 1)
			right = n - m - left
			if left < int(k / 2) or right < int(k / 2):
				continue
			is_can = True
			break
		if is_can:
			stdout.write('YES\n')
		else:
			stdout.write('NO\n')
main()


T = int(input())
for _ in range(T):
	(n, k, m) = map(int, input().split())
	b = [int(i) for i in input().split()]
	ff = False
	for (p, i) in enumerate(b):
		if i - p - 1 >= k >> 1 and n - i - len(b) + p + 1 >= k >> 1:
			ff = True
	if b == [int(i) + 1 for i in range(n)]:
		print('YES')
	elif k > 1 and (n - m) % (k - 1) == 0:
		if ff:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


import os, sys
from io import BytesIO, IOBase

def solve(n, k, m, b):
	if (n - m) % (k - 1):
		return 'NO'
	(val, val1, x) = (0, 0, k // 2)
	for i in range(1, n + 1):
		if i == b[val]:
			val += 1
			if val1 >= x and n - m - val1 >= x:
				return 'YES'
		else:
			val1 += 1
		if val == m:
			break
	return 'NO'

def main():
	for _ in range(int(input())):
		(n, k, m) = map(int, input().split())
		b = list(map(int, input().split()))
		print(solve(n, k, m, b))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	m = int(l[2])
	l = input().split()
	li = [int(i) for i in l]
	if (n - m) % (k - 1):
		print('NO')
		continue
	poss = 0
	for i in range(m):
		z = n - li[i]
		z -= m - i - 1
		y = li[i] - 1
		y -= i
		if z >= (k - 1) // 2 and y >= (k - 1) // 2:
			poss = 1
			break
	if poss:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.buffer.readline

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))
allAns = []
t = int(input())
for _ in range(t):
	(n, k, m) = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	b.append(n + 1)
	ans = 'NO'
	if (n - m) % (k - 1) == 0:
		leftMissing = 0
		rightMissing = n - m
		prev = 0
		for x in b:
			leftMissing += x - prev - 1
			rightMissing -= x - prev - 1
			prev = x
			if leftMissing >= (k - 1) // 2 and rightMissing >= (k - 1) // 2:
				ans = 'YES'
				break
	allAns.append(ans)
multiLineArrayPrint(allAns)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	(n, k, m) = sep()
	a = lis()
	have = set(a)
	if len(have) != m:
		print('NO')
		return
	notvis = []
	for i in range(1, n + 1):
		if i not in have:
			notvis.append(i)
	if len(notvis) % (k - 1):
		print('NO')
		return
	left = 0
	right = 0
	diff = []
	cnt = 1
	for i in range(1, len(notvis)):
		if notvis[i] == notvis[i - 1] + 1:
			cnt += 1
		else:
			diff.append(cnt)
			cnt = 1
	diff.append(cnt)
	ind = 0
	while left + diff[ind] < k // 2:
		left += diff[ind]
		ind += 1
	rnd = len(diff) - 1
	while right + diff[rnd] < k // 2:
		right += diff[rnd]
		rnd -= 1
	print('YES' if ind < rnd else 'NO')
testcase(int(inp()))


T = int(input())
for _ in range(T):
	(n, k, m) = map(int, input().split())
	b = [0] + list(map(int, input().split())) + [0] * 10
	cnt = 0
	l = [0] * (m + 10)
	r = [0] * (m + 10)
	for i in range(1, m + 1):
		cnt += b[i] - b[i - 1] - 1
		l[i] = l[i - 1] + b[i] - b[i - 1] - 1
	cnt += n - b[m]
	r[m] = n - b[m]
	for i in range(m - 1, 0, -1):
		r[i] = r[i + 1] + b[i + 1] - b[i] - 1
	flag = False
	for i in range(1, m + 1):
		if l[i] >= k // 2 and r[i] >= k // 2:
			flag = True
	if cnt % (k - 1) != 0:
		flag = False
	if flag:
		print('YES')
	else:
		print('NO')


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from itertools import accumulate
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import sys
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip().split()]

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
for _ in range(val()):
	(n, k, m) = li()
	b = set(li())
	ans = 0
	poss = []
	temp = n
	while temp > 0:
		poss.append(temp)
		temp -= k - 1
	if m not in poss:
		print('NO')
		continue
	left = 0
	right = n - m
	for i in range(1, n + 1, 1):
		if i in b:
			if left >= k // 2 and right >= k // 2:
				ans = 1
				break
		else:
			left += 1
			right -= 1
	print('YES' if ans else 'NO')


import sys

def load_sys():
	return sys.stdin.readlines()

def load_local():
	with open('input.txt', 'r') as f:
		input = f.readlines()
	return input

def km(n, k, m, B):
	if (n - m) % (k - 1) != 0:
		return 'NO'
	R = [0] * m
	L = [0] * m
	for i in range(m):
		R[i] = n - B[i] - (m - i - 1)
		L[i] = n - m - R[i]
		if R[i] >= k // 2 and L[i] >= k // 2:
			return 'YES'
	return 'NO'
input = load_sys()
idx = 1
N = len(input)
while idx < len(input):
	(n, k, m) = [int(x) for x in input[idx].split()]
	B = [int(x) for x in input[idx + 1].split()]
	idx += 2
	print(km(n, k, m, B))


from sys import stdin, stdout

def k_and_medians(n, k, m, b_a):
	if (n - m) % (k - 1) != 0:
		return False
	b_s = set(b_a)
	l_a = [0] * (n + 1)
	for i in range(1, n + 1):
		l_a[i] = l_a[i - 1]
		if i not in b_s:
			l_a[i] = l_a[i - 1] + 1
	r = 0
	for i in range(n, 0, -1):
		if i not in b_s:
			r += 1
		elif r >= (k - 1) // 2 and l_a[i] >= (k - 1) // 2:
			return True
	return False
t = int(stdin.readline())
for _ in range(t):
	(n, k, m) = map(int, stdin.readline().split())
	b_a = list(map(int, stdin.readline().split()))
	r = k_and_medians(n, k, m, b_a)
	if r:
		stdout.write('YES\n')
	else:
		stdout.write('NO\n')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k, m) = map(int, input().split())
	B = list(map(int, input().split()))
	if (n - m) % (k - 1):
		print('NO')
	else:
		p = (k - 1) // 2
		(left, right) = ([0] * m, [0] * m)
		for (i, b) in enumerate(B, 1):
			left[i - 1] = b - i
		for (i, b) in enumerate(B[::-1], 1):
			right[m - i] = n - i + 1 - b
		for i in range(m):
			if left[i] >= p and right[i] >= p:
				print('YES')
				break
		else:
			print('NO')


t = int(input())
res = []
for x1 in range(t):
	(n, k, m) = [int(i) for i in input().split()]
	eind = [int(i) for i in input().split()]
	x2 = len(eind)
	if (n - m) % (k - 1) != 0:
		res.append('NO')
	else:
		h = (k - 1) // 2
		i1 = 0
		a1 = 1
		tel1 = 0
		while tel1 < h and i1 < x2:
			if eind[i1] == a1:
				a1 += 1
				i1 += 1
			else:
				tel1 += 1
				a1 += 1
		if i1 >= x2:
			res.append('NO')
		else:
			a2 = eind[i1]
			tel2 = 0
			while tel2 < h and i1 < x2:
				if eind[i1] == a2:
					a2 += 1
					i1 += 1
				else:
					tel2 += 1
					a2 += 1
			if i1 == x2:
				tel2 += n - eind[i1 - 1]
			if tel2 >= h:
				res.append('YES')
			else:
				res.append('NO')
for i in res:
	print(i)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

	def __init__(self, file):
		self.newlines = 0
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

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

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

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

def print_list(l):
	print(' '.join(map(str, l)))
from math import ceil
for _ in range(N()):
	(n, k, m) = RL()
	a = RLL()
	k >>= 1
	if k == 0 or (n - m) % (2 * k):
		print('NO')
	else:
		t = n - m
		now = a[0] - 1
		flag = False
		a.append(n + 1)
		for i in range(1, m + 1):
			if k <= now <= t - k:
				flag = True
				break
			now += a[i] - a[i - 1] - 1
		print('YES' if flag else 'NO')


import sys
for _ in range(int(sys.stdin.readline().strip())):
	(n, k, m) = tuple(map(int, sys.stdin.readline().strip().split(' ')))
	ml = set(map(int, sys.stdin.readline().strip().split(' ')))
	havitada = []
	for i in range(1, n + 1):
		if i not in ml:
			havitada.append(i)
	saab = False
	if len(havitada) % (k - 1) != 0:
		print('no')
		continue
	for i in range(k // 2 - 1, len(havitada) - k // 2):
		if havitada[i + 1] - havitada[i] != 1:
			print('yes')
			break
	else:
		print('no')