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 ∈ [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} ... 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], ..., 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 ≠ y), or there exists such i (1 ≤ i ≤ min(|x|, |y|)), that x_i < y_i, and for any j (1 ≤ j < i) x_j = y_j.

Input

The first line contains one integer q (1 ≤ q ≤ 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 ≤ k ≤ n ≤ 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. 

Example

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
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

# available on Google, AtCoder Python3
# not available on Codeforces
# import numpy as np
# import scipy

# if testing locally, print to terminal with a different color
OFFLINE_TEST = getpass.getuser() == "hkmac"
# OFFLINE_TEST = False  # codechef does not allow getpass
def log(*args):  
    if OFFLINE_TEST:
        print('\033[36m', *args, '\033[0m', file=sys.stderr)


def solve_(srr, k):
    # your solution here
    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

    # t = Trie()
    h = min(k,20)

    bag = set()
    for i,x in enumerate(srr[k-h:], start=k-h):
        if i+h == len(srr)+1:
            break
        # i = max(0,i-1)
        forbidden = int(srr[i:i+h],2)
        log(srr[i:i+h])
        bag.add(forbidden)
        # log(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 ""

    # log(val)
    return bin(val)[2:].zfill(k)



def solve(*args):
    # screen input
    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)]

# for case_num in [1]:  # no loop over test case

skipping = True
for case_num in range(int(input())):
    # read line as a string

    # read one line and parse each word as a string
    # lst = input().split()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as an integer
    _,k = list(map(int,input().split()))
    srr = input().strip()

    # read multiple rows
    # mrr = read_matrix(k)
    # arr = read_strings(k)

    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)  # please change

    # if k == 24:
    #     exit()

    # print result
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Other platforms - no case number required
    if res:
        print("YES")
        print(res)
    else:
        print("NO")
    # print(len(res))  # if printing length of list
    # print(*res)  # if printing a list