Let's call two strings $a$ and $b$ (both of length $k$) a bit similar if they have the same character in some position, i. e. there exists at least one $i \in [1, k]$ such that $a_i = b_i$.

You are given a binary string $s$ of length $n$ (a string of $n$ characters 0 and/or 1) and an integer $k$. Let's denote the string $s[i..j]$ as the substring of $s$ starting from the $i$-th character and ending with the $j$-th character (that is, $s[i..j] = s_i s_{i + 1} s_{i + 2} \dots s_{j - 1} s_j$).

Let's call a binary string $t$ of length $k$ beautiful if it is a bit similar to all substrings of $s$ having length exactly $k$; that is, it is a bit similar to $s[1..k], s[2..k+1], \dots, s[n-k+1..n]$.

Your goal is to find the lexicographically smallest string $t$ that is beautiful, or report that no such string exists. String $x$ is lexicographically less than string $y$ if either $x$ is a prefix of $y$ (and $x \ne y$), or there exists such $i$ ($1 \le i \le \min(|x|, |y|)$), that $x_i < y_i$, and for any $j$ ($1 \le j < i$) $x_j = y_j$.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 10000$) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 10^6$). The second line contains the string $s$, consisting of $n$ characters (each character is either 0 or 1).

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


-----Output-----

For each test case, print the answer as follows:

if it is impossible to construct a beautiful string, print one line containing the string NO (note: exactly in upper case, you can't print No, for example);

otherwise, print two lines. The first line should contain the string YES (exactly in upper case as well); the second line — the lexicographically smallest beautiful string, consisting of $k$ characters 0 and/or 1.


-----Examples-----

Input
7
4 2
0110
4 2
1001
9 3
010001110
9 3
101110001
10 3
0101110001
10 10
1111111111
11 10
11111111110
Output
YES
11
YES
00
YES
010
YES
101
NO
YES
0000000001
YES
0000000010


-----Note-----

None

Difficulty: VERY_HARD
Tags: String algorithms

Bit manipulation

Amortized analysis

Complete search
Skill types: Bit manipulation

Amortized analysis

Complete search

Starter code:

Solutions:
import sys
input = sys.stdin.readline
from collections import Counter
import math
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	k = min(32, m)
	s = input().rstrip()
	D = set()
	v = 2 ** k - 1
	for i in range(m - k, len(s) - k + 1):
		temp = s[i:i + k]
		D.add(v - int(temp, 2))
	ok = 0
	cc = s[:m].count('0')
	if cc > 0:
		on = 1
	else:
		on = 0
	for i in range(len(s) - m):
		if cc == 0:
			on = 0
		if s[i] == '0':
			cc -= 1
		if s[i + m] == '0':
			cc += 1
		if cc == 0:
			on = 0
	if on == 1:
		print('YES')
		print(m * '0')
		ok = 1
	else:
		for i in range(v + 1):
			if i not in D:
				ans = bin(i)[2:]
				ans = (m - len(ans)) * '0' + ans
				print('YES')
				print(ans)
				ok = 1
				break
	if ok == 0:
		print('NO')


from itertools import accumulate, chain
BITS = 20
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	antis = [1 - int(si) for si in s]
	antis_s = ''.join(map(str, antis))
	antis_sums = tuple(chain((0,), accumulate(antis)))
	fbd = set()
	for i in range(n + 1 - k):
		if k < BITS or antis_sums[i] == antis_sums[i + k - BITS]:
			cur = int(antis_s[max(i, i + k - BITS):i + k], base=2)
			fbd.add(cur)
	ans = 0
	while ans in fbd:
		ans += 1
	t = bin(ans)[2:]
	if len(t) > k:
		print('NO')
	else:
		print('YES')
		print(t.rjust(k, '0'))


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7
for _ in range(II()):
	(n, k) = MI()
	s = SI()
	c0 = [0]
	for c in s:
		c0.append(c0[-1] + (c == '0'))
	d = min(30, k)
	ng = set()
	now = int(s[n - d:], 2)
	now ^= (1 << d) - 1
	if c0[n - d] - c0[n - k] == 0:
		ng.add(now)
	for i in range(n - d - 1, k - d - 1, -1):
		now >>= 1
		if s[i] == '0':
			now |= 1 << d - 1
		if c0[i] - c0[i + d - k]:
			continue
		ng.add(now)
	for a in range(1 << d):
		if a not in ng:
			print('YES')
			print(f'{a:b}'.zfill(k))
			break
	else:
		print('NO')


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	maxx_digit = min(21, k)
	maxx_so = 2 ** maxx_digit
	arr = stdin.readline()
	so = 0
	to = 2 ** k
	dct = {}
	lientiep = 0
	for i in range(k):
		so = so * 2 + 1 - int(arr[i])
		if so >= maxx_so:
			so -= maxx_so
	for j in range(k - maxx_digit):
		if arr[j] == '1':
			lientiep += 1
		else:
			lientiep = 0
	dau = k - maxx_digit
	if lientiep >= k - maxx_digit:
		dct[so] = 1
	for i in range(k, n):
		so = so * 2 + 1 - int(arr[i])
		if so >= maxx_so:
			so -= maxx_so
		if arr[dau] == '1':
			lientiep += 1
		else:
			lientiep = 0
		if lientiep >= k - maxx_digit:
			dct[so] = 1
		dau += 1
	ans = 0
	while ans in dct:
		ans += 1
	ans = bin(ans)[2:]
	if k < len(ans):
		print('NO')
	else:
		ans = '0' * (k - len(ans)) + ans
		print('YES')
		print(ans)


import sys
input = sys.stdin.readline
(T,) = map(int, input().split())
for _ in range(T):
	(N, K) = map(int, input().split())
	s = input().strip()
	hr = min(N - K + 2, 2 ** K)
	m = (1 << min(K, 20)) - 1
	x = 0
	over = 0
	for i in range(K):
		x <<= 1
		x += 1 - int(s[i])
		if m + 1 & x:
			over += 1
		x &= m
	vs = set()
	if not over:
		vs.add(x)
	for i in range(N - K):
		x <<= 1
		if m + 1 & x:
			over += 1
		x = x & m
		if 1 - int(s[i + K]):
			x += 1
		if 1 - int(s[i]):
			over -= 1
		if not over:
			vs.add(x)
	for i in range(hr):
		if i not in vs:
			print('YES')
			print(bin(i)[2:].zfill(K))
			break
	else:
		print('NO')


import sys
input = sys.stdin.readline
t = int(input())
outL = []
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().strip()
	bad = set()
	k2 = min(k, 20)
	last = -1
	curr = 0
	mask = (1 << k2) - 1
	for i in range(n):
		curr *= 2
		if s[i] == '0':
			curr += 1
		if curr > mask:
			curr &= mask
			last = i
		if i >= k - 1 and i - last >= k - k2:
			bad.add(curr)
	for i in range(1 << k2):
		if i not in bad:
			outL.append('YES')
			out = bin(i)[2:]
			outL.append('0' * (k - len(out)) + out)
			break
	else:
		outL.append('NO')
print('\n'.join(outL))


import sys
input = sys.stdin.readline
t = int(input())
for case in range(t):
	(n, k0) = [int(x) for x in input().split(' ')]
	starts = set([i for i in range(n - k0 + 1)])
	s = input()
	k = min(20, k0)
	if k < k0:
		nz = []
		cz = n
		for i in range(n - 1, -1, -1):
			if s[i] == '0':
				cz = i
			nz.append(cz)
		nz.reverse()
		for i in range(n - k0 + 1):
			if nz[i] < i + k0 - 20:
				starts.remove(i)
	Z = 1 << k
	avoid = set()
	for i in starts:
		r = int(s[i + k0 - k:i + k0], 2)
		avoid.add(Z - 1 - r)
	j = 0
	while j in avoid and j < Z:
		j += 1
	ans = bin(j)[2:]
	if j == Z:
		print('NO')
	else:
		print('YES')
		ans = '0' * (k0 - len(ans)) + ans
		print(ans)


import io
import os
import random

def solve1(N, K, S):
	bad = set()
	for i in range(N - K + 1):
		neg = ''.join(('10'[int(x)] for x in S[i:i + K]))
		bad.add(neg)
	for mask in range(2 ** K):
		s = bin(mask)[2:].rjust(K, '0')
		if s not in bad:
			return 'YES\n' + s
	return 'NO'

def solve(N, K, S):
	MOD = 10 ** 9 + 7
	BASE = random.randint(2, MOD - 1)

	def buildRK(S):
		pref = [0]
		for x in S:
			pref.append((pref[-1] * BASE + int(x)) % MOD)
		return pref

	def hash(pref, i, j):
		k = j - i
		powK = pow(BASE, k, MOD)
		return (pref[j] - pref[i] * powK) % MOD
	pref = buildRK(('1' if x == '0' else '0' for x in S))
	ones = buildRK('1' * K)
	bad = set()
	for i in range(N - K + 1):
		bad.add(hash(pref, i, i + K))
	maskHash = 0
	if maskHash not in bad:
		return 'YES\n' + '0' * K
	for mask in range(1, 2 ** K):
		prevMask = mask - 1
		trailingOnes = 0
		while prevMask & 1 << trailingOnes:
			trailingOnes += 1
		maskHash -= ones[trailingOnes]
		maskHash += pow(BASE, trailingOnes, MOD)
		maskHash %= MOD
		if DEBUG:
			s = bin(mask)[2:].rjust(K, '0')
			pref2 = buildRK(s)
			check = hash(pref2, 0, K)
			assert check == maskHash
		if maskHash not in bad:
			s = bin(mask)[2:].rjust(K, '0')
			return 'YES\n' + s
	return 'NO'
DEBUG = False
if DEBUG:
	import random
	random.seed(0)
	for _ in range(100000000):
		N = random.randint(1, 100)
		K = random.randint(1, 100)
		S = ''.join([str(random.randint(0, 1)) for i in range(N)])
		print(N, K, S)
		ans1 = solve1(N, K, S)
		ans = solve(N, K, S)
		assert ans1 == ans
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, K) = [int(x) for x in input().split()]
	S = input().decode().rstrip()
	ans = solve(N, K, S)
	print(ans)


import sys
input = sys.stdin.readline
q = int(input())
for tests in range(q):
	(n, k) = map(int, input().split())
	S = input().strip()
	MIN = min(1 << k, n + 1)
	BLIST = [0] * MIN
	ALL = (1 << k) - 1
	right = n - 1
	left = n - 1
	NOW = 0
	while right >= k - 1 and left >= 0:
		while right - left < k and right >= k - 1 and (left >= 0):
			if S[left] == '0':
				if right - left < 20:
					NOW += 1 << right - left
					left -= 1
				else:
					nright = min(left + 20, right - 1)
					NOW >>= right - nright
					right = nright
			else:
				left -= 1
		if NOW < MIN and right - left == k:
			BLIST[NOW] = 1
		NOW >>= 1
		right -= 1
	for i in range(MIN):
		if BLIST[i] == 1:
			continue
		else:
			print('YES')
			print(bin(i)[2:].zfill(k))
			break
	else:
		print('NO')


from math import ceil
from math import log
tests = int(input())
for testCounter in range(tests):
	splitted = [int(amit) for amit in input().split(' ')]
	n = splitted[0]
	k = splitted[1]
	instr = input()
	closestLeftZero = [-1] * len(instr)
	closestLeftZeroPos = -1
	for i in range(len(instr)):
		closestLeftZero[i] = closestLeftZeroPos
		if instr[i] == '0':
			closestLeftZeroPos = i
	z = n - k + 1
	m = int(min(k, ceil(log(z + 1, 2))))
	used = [False] * (1 << m)
	setTheseToZero = int(max(0, k - ceil(log(z + 1, 2))))
	hit = 0
	first = True
	numBits = 0
	toBeAndedWtih = 0
	for i in range(len(instr) - k + 1):
		if first:
			first = False
			hit = 0
			power = 0
			for j in range(i + k - 1, i + setTheseToZero - 1, -1):
				if instr[j] == '0':
					hit += 1 << power
				power += 1
				numBits += 1
			toBeAndedWtih = (1 << numBits) - 1
		else:
			hit <<= 1
			hit &= toBeAndedWtih
			if instr[i + k - 1] == '0':
				hit |= 1
		if closestLeftZero[i + setTheseToZero] < i:
			used[hit] = True
	ans = -1
	for i in range(len(used)):
		if used[i] == False:
			ans = i
			break
	if ans == -1:
		print('NO')
	else:
		print('YES')
		res = bin(ans)[2:]
		b4 = '0' * (k - len(res))
		res = b4 + res
		print(res)


import sys
input = sys.stdin.readline
a = int(input())
for case in range(a):
	(n, k0) = [int(x) for x in input().split(' ')]
	start_inds = set([i for i in range(n - k0 + 1)])
	s = input()
	k = min(20, k0)
	if k < k0:
		next_0 = []
		curr_0 = n
		for i in range(n - 1, -1, -1):
			if s[i] == '0':
				curr_0 = i
			next_0.append(curr_0)
		next_0.reverse()
		for i in range(n - k0 + 1):
			if next_0[i] < i + k0 - 20:
				start_inds.remove(i)
	Z = 1 << k
	avoid = set()
	for i in start_inds:
		r = int(s[i + k0 - k:i + k0], 2)
		avoid.add(Z - 1 - r)
	j = 0
	while j in avoid and j < Z:
		j += 1
	ans = bin(j)[2:]
	if j == Z:
		print('NO')
	else:
		print('YES')
		ans = '0' * (k0 - len(ans)) + ans
		print(ans)


T = int(input())
ans = []
for t in range(T):
	(n, k) = map(int, input().split())
	s = list(input())
	for i in range(n):
		if s[i] == '0':
			s[i] = '1'
		else:
			s[i] = '0'
	count1 = 0
	if k > 20:
		count1 = s[0:k - 20].count('1')
	s = ''.join(s)
	dic = {}
	for i in range(n - k + 1):
		if k <= 20:
			dic[int(s[i:i + k], 2)] = 0
		else:
			if count1 == 0:
				dic[int(s[i + k - 20:i + k], 2)] = 0
			count1 -= int(s[i])
			count1 += int(s[i + k - 20])
	tmpans = 10 ** 10
	for i in range(0, n + 1):
		if not i in dic:
			tmpans = i
			break
	if tmpans < pow(2, k):
		ans.append('YES')
		ans.append(format(tmpans, '0' + str(k) + 'b'))
	else:
		ans.append('NO')
for i in range(len(ans)):
	print(ans[i])


import sys, os, getpass
import heapq as hq
import math, random, functools, itertools
import collections
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve_(srr, k):
	srr = ''.join(['0' if x == '1' else '1' for x in srr])
	log(srr)
	candidate = '0' * k
	if not candidate in srr:
		return candidate
	candidate = '0' * (k - 1) + '1'
	if not candidate in srr:
		return candidate
	h = min(k, 20)
	bag = set()
	for (i, x) in enumerate(srr[k - h:], start=k - h):
		if i + h == len(srr) + 1:
			break
		forbidden = int(srr[i:i + h], 2)
		log(srr[i:i + h])
		bag.add(forbidden)
	for (i, a) in enumerate(sorted(bag)):
		if i != a:
			val = i
			break
	else:
		val = len(bag)
	log(bag)
	if len(bag) == 2 ** h:
		return ''
	return bin(val)[2:].zfill(k)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]
skipping = True
for case_num in range(int(input())):
	(_, k) = list(map(int, input().split()))
	srr = input().strip()
	if False and skipping and (srr == '10101111011010011110100111010110101011101000001101000001000111101100000010011001001100001110010001001'):
		for _ in range(5485):
			_ = input()
			_ = input()
		(n, k) = list(map(int, input().split()))
		srr = input().strip()
		print(n, k)
		print(srr)
		print(solve(srr, k))
	else:
		skipping = False
	res = solve(srr, k)
	if res:
		print('YES')
		print(res)
	else:
		print('NO')


def solve():
	(n, k) = [int(t) for t in input().split()]
	A = [int(c) for c in input()]
	for i in range(n):
		A[i] = 1 - A[i]
	ctz = []
	zeros = 0
	for x in reversed(A):
		if x == 0:
			zeros += 1
		else:
			zeros = 0
		ctz.append(zeros)
	ctz = ctz[::-1]
	S = n - k + 1
	L = S.bit_length()
	V = set()
	for i in range(n - k + 1):
		if ctz[i] >= k - L:
			v = 0
			d = 1
			pos = i + k - 1
			for _ in range(min(L, k)):
				v += d * A[pos]
				pos -= 1
				d *= 2
			V.add(v)
	for ans in range(2 ** k):
		if ans not in V:
			print('YES')
			res = bin(ans)[2:]
			res = '0' * (k - len(res)) + res
			print(res)
			break
	else:
		print('NO')
import sys, os, io
input = lambda : sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode('ascii'))
for _ in range(int(input())):
	solve()
os.write(1, stdout.getvalue())


import sys
input = sys.stdin.readline
import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()[:-1]
	m = min(k, math.ceil(math.log2(n - k + 2)))
	used = [0] * (1 << m)
	next0 = [float('inf')] * n
	if s[n - 1] == '0':
		next0[n - 1] = n - 1
	for j in range(n - 2, -1, -1):
		if s[j] == '0':
			next0[j] = j
		else:
			next0[j] = next0[j + 1]
	d = k - m
	for j in range(n - k + 1):
		if next0[j] - j < d:
			continue
		cur = 0
		for x in range(j + d, j + k):
			cur = cur * 2 + int(s[x])
		used[(1 << m) - 1 ^ cur] = 1
	ans = -1
	for j in range(1 << m):
		if not used[j]:
			ans = j
			break
	if ans == -1:
		print('NO')
	else:
		print('YES')
		s = '0' * d
		tmp = ''
		for j in range(m):
			tmp += '1' if ans & 1 else '0'
			ans >>= 1
		s += tmp[::-1]
		print(s)


def power(a, n, p):
	if n == 0:
		return 1
	x = power(a, n // 2, p)
	x = x * x % p
	if n % 2 == 1:
		x = x * a % p
	return x % p

def gcd_extended(a, b):
	if a == 0:
		return (b, 0, 1)
	(gcd, x1, y1) = gcd_extended(b % a, a)
	x = y1 - b // a * x1
	y = x1
	return (gcd, x, y)

def poly_hash(s, p, q):
	d = 1
	res = 0
	for c in s[::-1]:
		res += int(c) * d % p
		d = d * q % p
	return res

def slightly_similar(n, k, s):
	ls = map(int, list(s))
	s_inv = ''.join([str(1 - int(c)) for c in s])
	p = 998244353
	q = 3
	h = poly_hash(s_inv[:k], p, q)
	hashes = {h}
	l = 0
	r = k
	while r < n:
		h = (h * q - int(s_inv[l]) * q_k + int(s_inv[r])) % p
		hashes.add(h)
		l += 1
		r += 1
	a = 0
	b = bin(a)[2:]
	while len(b) <= k:
		if poly_hash(b, p, q) not in hashes:
			return ['YES', '0' * (k - len(b)) + b]
		a += 1
		b = bin(a)[2:]
	return ['NO']
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	p = 998244353
	q = 3
	q_k = power(q, k, p)
	ans = slightly_similar(n, k, s)
	for x in ans:
		print(x)


import random
for tc in range(int(input())):
	HASHMOD = random.getrandbits(128)
	(n, k) = map(int, input().split())
	s = input()
	hsh = 0
	for i in range(k):
		hsh <<= 1
		if s[i] == '0':
			hsh += 1
		hsh %= HASHMOD
	excluded = set([hsh])
	leftpop = pow(2, k, HASHMOD)
	for i in range(k, n):
		hsh <<= 1
		if s[i] == '0':
			hsh += 1
		if s[i - k] == '0':
			hsh -= leftpop
		hsh %= HASHMOD
		if hsh < 2 ** k:
			excluded.add(hsh)
	if len(excluded) == 2 ** k:
		print('NO')
	else:
		print('YES')
		for i in range(2 ** k):
			if i not in excluded:
				print(bin(i)[2:].zfill(k))
				break


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		(N, K) = map(int, input().split())
		S = input().rstrip('\n')
		if K <= 20:
			T = [int(s) ^ 1 for s in S]
			bad = set()
			t = 0
			for i in range(K):
				t += T[i] * (1 << K - i - 1)
			beki = 1 << K - 1
			for i in range(N - K + 1):
				bad.add(t)
				if i != N - K:
					t -= T[i] * beki
					t *= 2
					t += T[i + K]
			ok = 0
			for i in range(1 << K):
				if i not in bad:
					print('YES')
					print(bin(i)[2:].zfill(K))
					ok = 1
					break
			if not ok:
				print('NO')
		else:
			print('YES')
			T = [int(s) ^ 1 for s in S]
			bad = set()
			zero_left = [0] * N
			for (i, t) in enumerate(T[:-1]):
				if t == 0:
					zero_left[i + 1] = zero_left[i] + 1
			t = 0
			beki = 1 << 19
			for i in range(N - K + 1):
				if zero_left[i + K - 20] == K - 20:
					t = 0
					for j in range(20):
						t += T[i + K - 20 + j] * (1 << 20 - j - 1)
					bad.add(t)
				elif zero_left[i + K - 20] > K - 20:
					t -= T[i + K - 20 - 1] * beki
					t *= 2
					t += T[i + K - 1]
					bad.add(t)
			for i in range(1 << K):
				if i not in bad:
					print(bin(i)[2:].zfill(K))
					break
main()


def main():
	from sys import stdin
	input = stdin.readline

	def f(l, r):
		return p[r] - p[l - 1]
	vis = [0] * (1 << 20)
	for cur in range(1, int(input()) + 1):
		(n, k) = map(int, input().split())
		t = min(k, 20)
		s = input()[:-1]
		s = s[::-1]
		s = ''.join((str(int(i) ^ 1) for i in s))
		p = [0] * (n + 1)
		for i in range(n):
			p[i] = p[i - 1] + int(s[i])
		x = 0
		for i in range(t):
			x += int(s[i]) << i
		if not f(t, k - 1):
			vis[x] = cur
		for i in range(t, n + t - k):
			x += int(s[i]) << t
			x >>= 1
			if not f(i + 1, i + k - t):
				vis[x] = cur
		for i in range(1 << t):
			if vis[i] < cur:
				print('YES')
				print((''.join((str(i >> j & 1) for j in range(t))) + '0' * (k - t))[::-1])
				break
		else:
			print('NO')
main()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
out = []
for _ in range(int(input())):
	(N, K) = [int(s) for s in input().split()]
	S = input()
	K2 = min(K, 20)
	start_str = -1
	curr = 0
	max_bit = pow(2, K2) - 1
	no = set()
	for i in range(N):
		curr *= 2
		if S[i] == '0':
			curr += 1
		if curr > max_bit:
			curr &= max_bit
			start_str = i
		if i >= K - 1 and i - start_str >= K - K2:
			no.add(curr)
	flag = False
	for i in range(pow(2, K2)):
		if i not in no:
			out.append('YES')
			out.append('0' * (K - len(bin(i)[2:])) + bin(i)[2:])
			flag = True
			break
	if not flag:
		out.append('NO')
print('\n'.join(out))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().rstrip()
	if k <= 20:
		s = [1 - int(s[i]) for i in range(n)]
		pow_2 = [2 ** i for i in range(20)]
		val = set([])
		for i in range(n - k + 1):
			tmp = 0
			for j in range(i, i + k):
				tmp += pow_2[i + k - 1 - j] * s[j]
			val.add(tmp)
		for i in range(min(n - k + 10, 2 ** k)):
			if i not in val:
				tmp = bin(i)[2:]
				ans = ['0'] * (k - len(tmp)) + [tmp]
				print('YES')
				print(''.join(ans))
				break
		else:
			print('NO')
	else:
		s = [1 - int(s[i]) for i in range(n)]
		check = k - 20
		imos = [s[i] for i in range(n)]
		for i in range(1, n):
			imos[i] += imos[i - 1]
		val = set([])
		pow_2 = [2 ** i for i in range(20)]
		for i in range(n - k + 1):
			if imos[i + check - 1] - imos[i] + s[i] == 0:
				tmp = 0
				for j in range(i + check, i + k):
					tmp += s[j] * pow_2[i + k - 1 - j]
				val.add(tmp)
		for i in range(n - k + 10):
			if i not in val:
				tmp = bin(i)[2:]
				ans = ['0'] * (k - len(tmp)) + [tmp]
				print('YES')
				print(''.join(ans))
				break
		else:
			print('NO')


from collections import *
import sys
input = sys.stdin.readline

def ri():
	return int(input())

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

def z_algorithm(ss):
	res = [0] * len(ss)
	res[0] = len(ss)
	(i, j) = (1, 0)
	while i < len(ss):
		while i + j < len(ss) and ss[j] == ss[i + j]:
			j += 1
		res[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < len(ss) and k + res[k] < j:
			res[i + k] = res[k]
			k += 1
		(i, j) = (i + k, j - k)
	return res

def pattern_matching(ss, tt):
	assert '$' not in ss and '$' not in tt
	new_ss = tt + '$' + ss
	z_array = z_algorithm(new_ss)
	result = []
	for (i, zi) in enumerate(z_array):
		if i != 0 and zi == len(tt):
			result.append(i - len(tt) - 1)
	return result
q = ri()
for _ in range(q):
	(n, k) = rl()
	ss = input()
	if k <= 20:
		bad_values = set()
		mask_k = 2 ** k - 1
		for left in range(n):
			right = left + k
			if right > n:
				break
			bad_value = int(ss[left:right], 2) ^ mask_k
			bad_values.add(bad_value)
		for value in range(2 ** k):
			if value in bad_values:
				continue
			else:
				print('YES')
				print('{:b}'.format(value).zfill(k))
				break
		else:
			print('NO')
	else:
		dk = k - 20
		tt = dk * '1'
		possible_left_idxs = pattern_matching(ss, tt)
		bad_values = set()
		mask_20 = 2 ** 20 - 1
		for left in pattern_matching(ss, tt):
			l = left + dk
			r = l + 20
			if r > n:
				break
			bad_value = int(ss[l:r], 2) ^ mask_20
			bad_values.add(bad_value)
		for value in range(2 ** k):
			if value in bad_values:
				continue
			else:
				print('YES')
				print('{:b}'.format(value).zfill(k))
				break


import sys
input = sys.stdin.buffer.readline
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	a = list(input().decode()[:n])
	cc = max(0, k - 20)
	(can, one, rm) = (set(), 0, k - cc)
	for u in range(n - rm + 1):
		if one >= cc:
			p = 0
			for v in range(rm):
				p = p * 2 + (a[u + v] == '0')
			can.add(p)
		if a[u] == '1':
			one += 1
		else:
			one = 0
	res = '0' * cc
	for u in range(1 << rm):
		if u not in can:
			b = bin(u)[2:]
			res += '0' * (rm - len(b)) + b
			break
	if len(res) < k:
		print('NO')
	else:
		print('YES')
		print(''.join(res))


from collections import deque
T = int(input())
r = 1
maxdigit = 20

def fastfrac(a, b, M):
	numb = pow(b, M - 2, M)
	return a % M * (numb % M) % M

def getnum(k, s):
	n = len(s)
	dic = {}
	prefixnum = max(0, k - maxdigit)
	real = k - prefixnum
	maxreal = (1 << real) - 1
	front = 0
	pres = deque()
	for i in range(prefixnum):
		if s[i] == '1':
			pres.append(i)
	num = int(s[prefixnum:prefixnum + real], 2)
	if len(pres) == prefixnum:
		dic[maxreal - num] = 1
		if maxreal - num == front:
			front += 1
	for i in range(n - k):
		if prefixnum > 0:
			if pres and pres[0] == i:
				pres.popleft()
			if s[i + prefixnum] == '1':
				pres.append(i + prefixnum)
		num = num % ((maxreal + 1) // 2)
		num = 2 * num + int(s[i + k])
		if len(pres) < prefixnum:
			continue
		dic[maxreal - num] = 1
		while front in dic:
			front += 1
	if front > maxreal:
		return -1
	else:
		return front
while r <= T:
	(n, k) = map(int, input().split())
	s = input()
	ans = getnum(k, s)
	if ans >= 0:
		print('YES')
		subs = bin(ans)[2:]
		subs = '0' * (k - len(subs)) + subs
		print(subs)
	else:
		print('NO')
	r += 1


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint

def main():
	(n, k) = map(int, input().split())
	s = input()
	st = set()
	x = min(k, 25)
	i = n
	while i - x >= 0:
		st.add(s[i - x:i])
		i -= 1
	bol = True
	c = 0
	for i in range(n):
		if s[i] == '0':
			c += 1
		if i - k >= 0 and s[i - k] == '0':
			c -= 1
		if i - k + 1 >= 0 and c <= 0:
			bol = False
	if bol:
		print('YES')
		print('0' * k)
		return
	for i in range(1 << x):
		b = ['1'] * x
		for j in range(x):
			if i & 1 << j:
				b[x - 1 - j] = '0'
		b = ''.join(b)
		if b not in st:
			c = ['1'] * x
			for j in range(x):
				if b[j] == '1':
					c[j] = '0'
			print('YES')
			print('0' * (k - x) + ''.join(c))
			return
	print('NO')
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')
for _ in range(int(input())):
	main()


import sys
from sys import stdin
import random
tt = int(stdin.readline())
for loop in range(tt):
	modA = 998244353
	modB = (modA + random.randint(100, 1000)) * 2 + 1
	(n, k) = map(int, stdin.readline().split())
	dA = pow(2, k, modA)
	dB = pow(2, k, modB)
	s = list(map(int, list(stdin.readline()[:-1])))
	for i in range(n):
		s[i] = 1 ^ s[i]
	sa = 0
	dicA = set()
	sb = 0
	dicB = set()
	for i in range(k):
		sa *= 2
		sb *= 2
		sa += s[i]
		sb += s[i]
		sa %= modA
		sb %= modB
	dicA.add(sa)
	dicB.add(sb)
	for i in range(n - k):
		sa *= 2
		sb *= 2
		sa += s[i + k]
		sb += s[i + k]
		sa -= dA * s[i]
		sb -= dB * s[i]
		sa %= modA
		sb %= modB
		dicA.add(sa)
		dicB.add(sb)
	for i in range(2 ** k):
		if i % modA not in dicA or i % modB not in dicB:
			print('YES')
			print(format(i, 'b').zfill(k))
			break
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = list(map(int, list(input())[:-1]))
	res = [0] * K
	ln = min(K, 25)
	s = set()
	cs = [0] * (N + 1)
	for i in range(N):
		cs[i + 1] = cs[i] + S[i]
	for i in range(N - K + 1):
		if cs[i + K - ln] - cs[i] < K - ln:
			continue
		t = S[i + K - ln:i + K]
		x = 0
		for j in range(ln):
			x |= t[j] << ln - j - 1
		s.add(x)
	for x in range((1 << ln) - 1, -1, -1):
		if x in s:
			continue
		print('YES')
		bn = list(bin(x))[2:]
		bn = [0] * (ln - len(bn)) + bn
		print(''.join([str(int(i) ^ 1) for i in bn]).zfill(K))
		break
	else:
		print('NO')