You have an array $a$ of size $n$ consisting only of zeroes and ones and an integer $k$. In one operation you can do one of the following:

Select $2$ consecutive elements of $a$ and replace them with their minimum (that is, let $a := [a_{1}, a_{2}, \ldots, a_{i-1}, \min(a_{i}, a_{i+1}), a_{i+2}, \ldots, a_{n}]$ for some $1 \le i \le n-1$). This operation decreases the size of $a$ by $1$.

Select $k$ consecutive elements of $a$ and replace them with their maximum (that is, let $a := [a_{1}, a_{2}, \ldots, a_{i-1}, \max(a_{i}, a_{i+1}, \ldots, a_{i+k-1}), a_{i+k}, \ldots, a_{n}]$ for some $1 \le i \le n-k+1$). This operation decreases the size of $a$ by $k-1$.

Determine if it's possible to turn $a$ into $[1]$ after several (possibly zero) operations.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2 \le k \le n \le 50$), the size of array $a$ and the length of segments that you can perform second type operation on.

The second line contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($a_i$ is $0$ or $1$), elements of array $a$.


-----Output-----

For each test case, if it is possible to turn $a$ into $[1]$, print "YES", otherwise print "NO".


-----Examples-----

Input
7
3 2
0 1 0
5 3
1 0 1 1 0
2 2
1 1
4 4
0 0 0 0
6 3
0 0 1 0 0 1
7 5
1 1 1 1 1 1 1
5 3
0 0 1 0 0
Output
YES
YES
YES
NO
YES
YES
YES


-----Note-----

In the first test case, you can perform the second type operation on second and third elements so $a$ becomes $[0, 1]$, then you can perform the second type operation on first and second elements, so $a$ turns to $[1]$.

In the fourth test case, it's obvious to see that you can't make any $1$, no matter what you do.

In the fifth test case, you can first perform a type 2 operation on the first three elements so that $a$ becomes $[1, 0, 0, 1]$, then perform a type 2 operation on the elements in positions two through four, so that $a$ becomes $[1, 1]$, and finally perform the first type operation on the remaining elements, so that $a$ becomes $[1]$.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms


Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if 1 in a:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if 1 in l:
		print('YES')
	else:
		print('NO')


n = int(input())
answer = []
for i in range(n):
	(x, y) = input().split()
	a = input().split()
	if '1' in a:
		answer.append('YES')
	else:
		answer.append('NO')
for i in answer:
	print(i)


import sys
num_of_cases = int(sys.stdin.readline().rstrip())
for _ in range(num_of_cases):
	ans = ''
	vars = sys.stdin.readline()
	nums = sys.stdin.readline().rstrip()
	print('YES' if '1' in nums else 'NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [x for x in input().split()]
	for x in a:
		if x[0] == '1':
			print('YES')
			break
	else:
		print('NO')


for t in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if 1 in l:
		print('YES')
	else:
		print('NO')


import sys
n = int(sys.stdin.readline())
for _ in range(n):
	(n, k) = list(map(int, sys.stdin.readline().split()))
	a = list(map(int, sys.stdin.readline().split()))
	if sum(a) == 0:
		print('NO')
	else:
		print('YES')


def main():
	for i in range(int(input())):
		test()

def test():
	(n, k) = map(int, input().split(' '))
	l = map(int, input().split(' '))
	for i in l:
		if i == 1:
			print('YES')
			return
	print('NO')
main()


t = int(input())
ans = []
for _ in range(t):
	(n, k) = tuple(map(int, input().split()))
	l = list(map(int, input().split()))
	if 1 in l:
		ans.append('YES')
	else:
		ans.append('NO')
for i in ans:
	print(i)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	if s.count(1) >= 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().replace(' ', ' ')
	if '1' not in s:
		print('NO')
	else:
		print('YES')


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	if 1 in l:
		print('YES')
	else:
		print('NO')


test_numbers = int(input())
results = []
for i in range(test_numbers):
	inputs = list(map(int, input().split(' ')))
	length = inputs[0]
	k = inputs[1]
	numbers = list(map(int, input().split(' ')))
	result = False
	for number in numbers:
		if number == 1:
			result = True
			break
	results.append(result)
for result in results:
	if result == True:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	data = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	if 1 in nums:
		print('YES')
	else:
		print('NO')
	t = t - 1


t = int(input())
for i in range(t):
	(a, k) = map(int, input().split())
	P = list(map(int, input().split()))
	if 1 in P:
		if len(P) == 1:
			print('YES')
		elif len(P) % k == 0:
			print('YES')
		elif len(P) >= k:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
result = []
for i in range(t):
	(n, k) = list(map(int, input().split(' ')))
	ai = list(map(int, input().split(' ')))
	if (k == 1) & (ai.count(1) == n):
		result.append('YES')
	elif (ai.count(1) >= 1) & (k > 1):
		result.append('YES')
	else:
		result.append('NO')
for i in result:
	print(i)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	ar = list(map(int, input().split()))
	if max(ar) == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
ans = []
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if 1 in a:
		ans.append('YES')
	else:
		ans.append('NO')
print(*ans, sep='\n')


import sys
input = sys.stdin.readline

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

def solution(k, a_len, a):
	if 1 in set(a):
		print('YES')
	else:
		print('NO')
t = int(input())
for _ in range(t):
	(a_len, k) = inlt()
	a = inlt()
	solution(k, a_len, a)


m = int(input())
for i in range(m):
	(n, k) = input().split()
	a = ['0' for l in range(int(n))]
	a = input().split()
	flag = 'YES'
	if '1' in a:
		print(flag)
	elif '1' not in a and k == '1':
		print(flag)
	else:
		print('NO')


t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	c1 = list1.count(1)
	if c1 >= 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	if 1 in l:
		print('YES')
	else:
		print('NO')


def main():
	t = int(input())
	result = []
	for _ in range(t):
		(n, k) = map(int, input().split())
		a = input()
		result.append(is_corrrect(n, k, a))
	for res in result:
		print(res)

def is_corrrect(n: int, k: int, a: list):
	return 'YES' if '1' in a else 'NO'
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	one = 0
	for i in arr:
		if i == 1:
			one += 1
	if one > 0:
		print('YES')
	else:
		print('NO')


test = int(input())
while test:
	test -= 1
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	cnt = a.count(1)
	if k == 1:
		if cnt == n:
			print('YES')
	elif cnt > 0:
		print('YES')
	else:
		print('NO')


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


import math
import os
q = int(input())
for x in range(q):
	(r, f) = map(int, input().split())
	l1 = list(map(int, input().split()))
	g1 = l1.count(1)
	if g1 >= 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 1:
		if sum(arr) == n:
			print('YES')
		else:
			print('NO')
	elif k > 1:
		if arr.count(1) >= 1:
			print('YES')
		else:
			print('NO')


S = int(input())
for _ in range(S):
	(R, A) = map(int, input().split())
	V = list(map(int, input().split()))
	temp = 0
	for i in range(len(V)):
		if V[i] == 1:
			temp = 1
			break
	if temp:
		print('YES')
	else:
		print('NO')


for ipopo in range(int(input())):
	(nap, ma) = [int(ipopo) for ipopo in input().split()]
	alpha = [int(ipopo) for ipopo in input().split()]
	if 1 in alpha:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	input()
	print('YES' if 1 in map(int, input().split()) else 'NO')


n = int(input())
while n > 0:
	n -= 1
	(n1, k) = map(int, input().split())
	a = list(map(int, input().split()))[:n1]
	if a.count(1) > 0:
		print('YES')
	else:
		print('NO')


k = int(input())
for i in range(k):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	if sum(c) > 0:
		print('YES')
	else:
		print('NO')


num_tests = int(input())
for _ in range(num_tests):
	params = input().split()
	arr = input().split()
	if '1' in arr:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	cnt = 0
	for i in range(n):
		cnt += arr[i]
	if cnt == 0:
		return 'NO'
	else:
		return 'YES'
for _ in range(int(input())):
	print(solve())


t = int(input())
for _ in range(t):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if 1 in b:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = sorted(l)
	if l1[a - 1] == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b) = map(int, input().rstrip().split())
	list1 = list(map(int, input().rstrip().split()))
	if list1.count(1) > 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print('NYOE S'[any((i == '1' for i in input())) and k > 1::2])


import sys

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

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

def get_string():
	return sys.stdin.readline().strip()
t = int(input())
while t:
	t -= 1
	(n, k) = get_ints()
	a = get_arr()
	check = False
	for i in range(0, n):
		if a[i] == 1:
			check = True
	if check:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(n, k) = map(int, input().split())
	lst = [int(i) for i in input().split()]
	if 1 in lst:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	if max(arr) == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split(sep=' ')))
	a = list(map(int, input().split(sep=' ')))
	if a.count(1) == 0:
		print('NO')
	else:
		print('YES')


c = int(input())
for i in range(c):
	(x, y) = map(int, input().split())
	string = input()
	if '1' in string:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, k) = (int(i) for i in input().split())
	a = input().split()
	res = 'YES' if a.count('0') != n else 'NO'
	print(res)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	if 1 not in list1:
		print('NO')
	else:
		print('YES')


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	if 1 not in A:
		print('NO')
		t -= 1
		continue
	print('YES')
	t -= 1


n = int(input())
for i in range(n):
	(m, k) = map(int, input().split())
	a = input()
	if '1' in a:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	b = input()
	a = list(input())
	if a.count('1') >= 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	_ = input()
	arr = input()
	print('YES' if arr.count('1') > 0 else 'NO')


for i in [*open(0)][2::2]:
	k = list(map(int, i.split()))
	print('YES' if 1 in k else 'NO')


num = int(input())
for i in range(num):
	(a, b) = map(int, input().split())
	arr = map(int, input().split())
	stack = []
	counter = 0
	for j in arr:
		if counter == 0:
			stack.append(j)
			counter = counter + 1
		elif stack[0] < j:
			stack[0] = j
	if stack[0] == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	print(['NO', 'YES'][1 in lst])


for _ in range(int(input())):
	input()
	print('YES' if '1' in input() else 'NO')


for test in range(int(input())):
	input()
	if input().find('1') == -1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if sum(arr) > 0:
		print('YES')
	else:
		print('NO')


class Solution:

	def solve(n: int, k: int, line: str):
		if '1' in line:
			return 'YES'
		return 'NO'

	def maxmina():
		for i in range(int(input())):
			(n, k) = list(map(int, input().split()))
			line = input().split()
			print(Solution.solve(n, k, line))
Solution.maxmina()