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

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.util.stream.*;
import java.math.*;
import static java.util.stream.Collectors.*;
 
public class Problem5New {
    public static void main(String[] args) {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        // PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
 
        try {
            int nbTests = Integer.parseInt(in.readLine());
            for (int i=0;i<nbTests;i++) {
                String[] tokens = in.readLine().split(" ");
                int n = Integer.parseInt(tokens[0]);
                int k = Integer.parseInt(tokens[1]);
                final String s = in.readLine();
                int maxLength = k;
                if (32-Integer.numberOfLeadingZeros(n-k+2)<k) {
                    maxLength = 32-Integer.numberOfLeadingZeros(n-k+2);
                }
                final int diff = k-maxLength;
                String result = findWithBitSet(s, k, diff);
                // String result = findWithByteArray(s, k, diff);
                // String result = findSmallestBI(inverseString(s), k, diff);
                if (result.length()>0) {
                    System.out.println("YES");
                    System.out.println("0".repeat(k-result.length())+result);
                } else {
                    System.out.println("NO");
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static String inverseString(String s) {
        StringBuffer buffer = new StringBuffer();
        for (int j=0;j<s.length();j++) {
            if (s.charAt(j)=='0') {
                buffer.append("1");
            } else {
                buffer.append("0");
            }
        }
        return buffer.toString();
    }

    public static String findWithBitSet(String s, int k, int prefix) {
        int n = s.length();
        final BitSet b = new BitSet(n);
        // init b
        IntStream.iterate(-1,x->s.indexOf("0",x+1))
            .skip(1)
            .takeWhile(x->x!=-1)
            //.peek(x->System.out.println("bits: "+x))
            .forEach(x->b.set(n-x-1));
            //System.out.println("BitSet: "+b);
        // create set
        final BitSet mask = new BitSet(k);
        IntStream.iterate(0,x->x+1).takeWhile(x->x<prefix).forEach(x->mask.set(k-x-1));
        HashSet<Long> set = new HashSet<>(10*n);
        BitSet bs;
        int j = 0;
        while (j<=n-k) {
            bs = b.get(j+k-prefix,j+k);
            if (bs.previousSetBit(prefix-1)==-1) {
                long[] l = b.get(j, j+k-prefix).toLongArray();
                if (l.length==0) {
                    set.add(0l);
                } else {
                    set.add(l[0]);
                }
                j++;
            } else {
                j+=bs.previousSetBit(prefix-1)+1;
            }
        }
        // check each number
        String found = LongStream.iterate(0,x->x+1)
                .takeWhile(x->x<Math.pow(2,k-prefix))
                .filter(x->!set.contains(x))
                .limit(1)
                .mapToObj(x->Long.toBinaryString(x))
                //.map(x->"0".repeat(k-x.length())+x)
                .collect(joining());
        return found;
    }
 
    public static String findSmallestTree(String s, int k) {
        char[] c = new char[k];
        Arrays.fill(c, '0');
        Vector<Vector<Integer>> allDepth = new Vector<Vector<Integer>>();
        String cs = String.valueOf(c);
        completeAllDepth(s, k, cs, allDepth);
        while (true) {
            if (allDepth.lastElement().size()==0) {
                return cs;
            } else {
                // iterate -> find last 0
                int index = -1;
                for (int i=k-1;i>=0;i--) {
                    if (c[i]=='0') {
                        index = i;
                        break;
                    }
                }
                if (index==-1) {
                    // scanned all!
                    return "";
                } else {
                    c[index] = '1';
                    Arrays.fill(c,index+1,k,'0');
                    cs = String.valueOf(c);
                    // truncate allDepth
                    for (int i=allDepth.size()-1;i>=index;i--) {
                        allDepth.remove(i);
                    }
                    completeAllDepth(s, k, cs, allDepth);
                }
            }
        }
    }

    public static void completeAllDepth(String s, int k, String cs, Vector<Vector<Integer>> allDepth) {
        int depth = allDepth.size();
        if (depth==0) {
            Vector<Integer> newV = new Vector<Integer>();
            int index = s.indexOf(cs.charAt(0), 0);
            while (index!=-1) {
                if (index<s.length()-k+1) {
                    newV.add(index);
                }
                index = s.indexOf(cs.charAt(0), index+1);
            }
            allDepth.add(newV);
        }
        for (int i=depth;i<k;i++) {
            Vector<Integer> newV = new Vector<Integer>();
            for (Iterator<Integer> it=allDepth.lastElement().iterator();it.hasNext();) {
                int index = it.next();
                if (cs.startsWith(s.substring(index, index+i+1))) {
                    newV.add(index);
                }
            }
            allDepth.add(newV);
        }
    }

    public static String findSmallestBI(String s, int k, int prefix) {
        HashSet<BigInteger> set = new HashSet<BigInteger>(10*s.length());
        BigInteger mask = new BigInteger("1".repeat(prefix)+"0".repeat(k-prefix));
        int length = s.length()-k+1;
        BigInteger bi = new BigInteger(s.substring(0, k),2);
        for (int j=1;j<length;j++) {
            if (bi.and(mask).equals(BigInteger.ZERO)) {
                set.add(bi.andNot(mask));
            }
            if (bi.testBit(k-1)) {
                bi = bi.clearBit(k-1);
            }
            bi = bi.shiftLeft(1);
            if (s.charAt(j+k-1)=='1') {
                bi = bi.setBit(0);
            }
        }
        if (bi.and(mask).equals(BigInteger.ZERO)) {
            set.add(bi.andNot(mask));
        }
        BigInteger scan = BigInteger.ZERO;
        while (true) {
            if (!set.contains(scan)) {
                String bis = scan.toString(2);
                if (bis.length()>k-prefix) {
                    return "";
                }
                bis = "0".repeat(k-bis.length()) + bis;
                return bis;
            } else {
                scan = scan.add(BigInteger.ONE);
            }
        }
    }    

    public static String findSmallestString(String s, int k) {
        char[] c = new char[k];
        Arrays.fill(c, '0');
        while (true) {
            if (!s.contains(String.valueOf(c))) {
                return String.valueOf(c);
            } else {
                // find last 0
                int index = -1;
                for (int i=k-1;i>=0;i--) {
                    if (c[i]=='0') {
                        index = i;
                        break;
                    }
                }
                if (index==-1) {
                    // scanned all!
                    return "";
                } else {
                    Arrays.fill(c,index+1,k,'0');
                    c[index] = '1';
                }
            }
        }
    }

    public static String findWithByteArray(String s, int k, int prefix) {
        ByteArray ba = ByteArray.valueOf(s).inverse();
        int[] found = new int[1<<k-prefix];
        Arrays.fill(found, 0);
        ByteArray mask = ByteArray.valueOf("1".repeat(prefix)+"0".repeat(k-prefix));
        for (long l=0;l<ba.length()-k+1;l++) {
            if (!ba.subba(l,l+k).and(mask)) {
                int value = ba.subba(l+prefix,l+k).toInt();
                if (value!=-1) {
                    found[(int) value] = 1;
                }
            }
        }
        //System.out.println("found: "+IntStream.of(found).mapToObj(x->(x==1?"1":"0")).collect(Collectors.joining()));
        int index = -1;
        for (int j=0;j<found.length;j++) {
            if (found[j]==0) {
                index = j;
                break;
            }
        }
        if (index!=-1) {
            return Long.toBinaryString(index);
        } else {
            return "";
        }
    }

    static class ByteArray {
     
        byte[] b;
        long startIndex, endIndex;
        
        private ByteArray(long length) {
            int size = (int) Math.ceil(length/8.);
            b = new byte[size];
            Arrays.fill(b,(byte)0);
            this.startIndex = 0;
            this.endIndex = length;
        }

        private ByteArray(ByteArray ba, long startIndex, long endIndex) {
            this.b = ba.b;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        private ByteArray(String s) {
            this(s.length());
            long index = 0;
            char[] c = s.toCharArray();
            for (char ca : c) {
                if (ca=='1') {
                    setBit(index);
                }
                index++;
            }
        }

        public static ByteArray valueOf(String s) {
            return new ByteArray(s);
        }

        /* public long indexOfOne() {
            for (long j=startIndex;j<endIndex;j=((j+8)/8)*8) {
                int by = b[(int) j/8] & 0xff;
                if (by>0) {
                    for (long k=(j/8)*8;k<(j/8)*8+8;k++) {
                        if (getBit(k)) {
                            return k;
                        }
                    }
                }
            }
            return -1;
        }*/

        public long length() {
            return endIndex-startIndex;
        }

        // inverse the values
        public ByteArray inverse() {
            ByteArray ba = new ByteArray(length());
            int index = 0;
            for (byte by : b) {
                ba.b[index++] = (byte) (by ^ 0xff);
            }
            return ba;
        }

        // reverse the valueorder of the bits
        public ByteArray reverse() {
            long size = endIndex-startIndex;
            ByteArray ba = new ByteArray(size);
            for (long i = 0;i<size;i++) {
                if (getBit(i)) {
                    ba.setBit(size-1-i);
                }
            }
            return ba;
        }

        private void setBit(long index) {
            index += startIndex;
            assert index<endIndex;
            int by = b[(int) (index/8)] & 0xff;
            by = by | (1<<(7-(index % 8)));
            b[(int) (index/8)] = (byte) by;
        }

        private void clearBit(long index) {
            index += startIndex;
            assert index<endIndex;
            int by = b[(int) (index/8)] & 0xff;
            by &= (1<<(7-(index%8))) ^ 0xff;
            b[(int) (index/8)] = (byte) by;
        }

        private boolean getBit(long index) {
            index += startIndex;
            assert index<endIndex;
            int by = b[(int) (index/8)] & 0xff;
            return (by & (1<<(7-(index%8))))!=0;
        }

        public ByteArray subba(long i1, long i2) {
            return new ByteArray(this, i1, i2);
        }

        public boolean and(ByteArray ba) {
            boolean result = false;
            for (long i=0;i<length();i++) {
                if (i<ba.length()) {
                    if (this.getBit(length()-i-1)&&ba.getBit(ba.length()-i-1)) {
                        return true;
                    }
                }
            }
            return false;
         }

        private static int[] clearTopBits = new int[]{255, 127, 63, 31, 15, 7, 3, 1, 0};

        public long toLong() {
            long sum = 0;
            //System.out.println(this +"to long:");
            for (long j=startIndex;j<endIndex;j=((j+8)/8)*8) {
                int by = b[(int) j/8] & 0xff;
                //System.out.println("by1: "+by+", j: "+j);
                by &= clearTopBits[(int) j%8];
                //System.out.println("by2: "+by);
                sum = sum*256 + by;
                //System.out.println("sum1: "+sum+", endIndex: "+endIndex);
                if (((j+8)/8)*8>endIndex) {
                    sum /= 1<<(8-(endIndex%8));
                    //System.out.println("sum2: "+sum);
                }
                //System.out.println("by: "+by+", j: "+j+", sum: "+sum);
            }
            return sum;
        }

        public int toInt() {
            long sum = 0;
            for (long j=startIndex;j<endIndex;j=((j+8)/8)*8) {
                int by = b[(int) j/8] & 0xff;
                by &= clearTopBits[(int) j%8];
                sum = sum*256 + by;
                if (((j+8)/8)*8>endIndex) {
                    sum /= 1<<(8-(endIndex%8));
                }
                if (sum>Integer.MAX_VALUE) {
                    return -1;
                }
            }
            return (int) sum;
        }


        @Override
        public String toString() {
            StringBuffer buffer = new StringBuffer();
            for (long i=0;i<length();i++) {
                if (getBit(i)) {
                    buffer.append("1");
                } else {
                    buffer.append("0");
                }
            }
            return buffer.toString();
        }
    }
}

/* import java.io.*;
import java.util.*; 
 
public class Problem5 {

    public static class Node {
        public Node childZero = null;
        public Node childOne = null;
        public Node parent = null;
        public Node(Node parent) {
            this.parent = parent;
        }
    }

    public static void main(String[] args) {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        // PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        try {
            int nbTests = Integer.parseInt(in.readLine());
            for (int i=0;i<nbTests;i++) {
                String[] tokens = in.readLine().split(" ");
                int n = Integer.parseInt(tokens[0]);
                int k = Integer.parseInt(tokens[1]);
                String s = in.readLine();
                StringBuffer buffer = new StringBuffer();
                for (int j=0;j<s.length();j++) {
                    if (s.charAt(j)=='0') {
                        buffer.append("1");
                    } else {
                        buffer.append("0");
                    }
                }
                s = buffer.toString();
                String smallest = findSmallest(s, k);
                if (smallest.length()>0) {
                    System.out.println("YES");
                    System.out.println(smallest);
                } else {
                    System.out.println("NO");
                }
            }
         } catch (Exception e) {

        }
    }

    public static String findSmallest(String s, int k) {
        Node root = new Node(null);
        int length = s.length()-k+1;
        for (int j=0;j<length;j++) {
            String sub = s.substring(j, j+k);
            // add string
            Node node = root;
            for (int i=0;i<sub.length();i++) {
                char c = sub.charAt(i);
                if (c=='0') {
                    if (node.childZero==null) {
                        node.childZero = new Node(node);
                    }
                    node = node.childZero;
                } else {
                    if (node.childOne==null) {
                        node.childOne = new Node(node);
                    }
                    node = node.childOne;
                }
            } 
        }
        char[] c = new char[k];
        Arrays.fill(c, '0');
        return findString(root, k, c, 0);
    }
    
    public static String findString(Node node, int k, char[] c, int depth) {
        // find string
        if (depth==k) {
            int last = String.valueOf(c).lastIndexOf("0");
            // backtracking
            if (last!=-1) {
                for (int i=k-1;i>last;i--) {
                    node = node.parent;
                    depth--;
                    c[i] = '0';
                }
                c[last] = '1';
                if (node.parent.childOne==null) {
                    return String.valueOf(c);
                } else {
                    node = node.parent.childOne;
                    return findString(node, k, Arrays.copyOf(c,k), depth);
                }
            } else {
                return "";
            }
        } else {
            if (node.childZero!=null) {
                return findString(node.childZero, k, Arrays.copyOf(c,k), depth+1);
            } else {
                return String.valueOf(c);
            }
        }
    }
}
*/