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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskE solver = new TaskE();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class TaskE {
        static boolean leq(int a1, int a2, int b1, int b2) {
            return a1 < b1 || a1 == b1 && a2 <= b2;
        }

        static boolean leq(int a1, int a2, int a3, int b1, int b2, int b3) {
            return a1 < b1 || a1 == b1 && leq(a2, a3, b2, b3);
        }

        static void radixPass(int[] a, int[] b, int[] r, int offset, int n, int K) {
            int[] cnt = new int[K + 1];
            for (int i = 0; i < n; i++) ++cnt[r[a[i] + offset]];
            for (int i = 1; i < cnt.length; i++) cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; i--) b[--cnt[r[a[i] + offset]]] = a[i];
        }

        private static void suffixArray(int[] T, int[] SA, int n, int K) {
            int n0 = (n + 2) / 3;
            int n1 = (n + 1) / 3;
            int n2 = n / 3;
            int n02 = n0 + n2;

            //******* Step 0: Construct sample ********
            // generate positions of mod 1 and mod 2 suffixes
            // the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
            int[] R = new int[n02 + 3];
            for (int i = 0, j = 0; i < n + (n0 - n1); i++)
                if (i % 3 != 0)
                    R[j++] = i;

            //******* Step 1: Sort sample suffixes ********
            // lsb radix sort the mod 1 and mod 2 triples
            int[] SA12 = new int[n02 + 3];
            radixPass(R, SA12, T, 2, n02, K);
            radixPass(SA12, R, T, 1, n02, K);
            radixPass(R, SA12, T, 0, n02, K);

            // find lexicographic names of triples and
            // write them to correct places in R
            int name = 0;
            for (int i = 0; i < n02; i++) {
                if (i == 0 || T[SA12[i]] != T[SA12[i - 1]] || T[SA12[i] + 1] != T[SA12[i - 1] + 1]
                        || T[SA12[i] + 2] != T[SA12[i - 1] + 2]) {
                    ++name;
                }
                R[SA12[i] / 3 + (SA12[i] % 3 == 1 ? 0 : n0)] = name;
            }

            if (name < n02) {
                // recurse if names are not yet unique
                suffixArray(R, SA12, n02, name);
                // store unique names in R using the suffix array
                for (int i = 0; i < n02; i++) R[SA12[i]] = i + 1;
            } else {
                // generate the suffix array of R directly
                for (int i = 0; i < n02; i++) SA12[R[i] - 1] = i;
            }

            //******* Step 2: Sort nonsample suffixes ********
            // stably sort the mod 0 suffixes from SA12 by their first character
            int[] R0 = new int[n0];
            for (int i = 0, j = 0; i < n02; i++)
                if (SA12[i] < n0)
                    R0[j++] = 3 * SA12[i];
            int[] SA0 = new int[n0];
            radixPass(R0, SA0, T, 0, n0, K);

            //******* Step 3: Merge ********
            // merge sorted SA0 suffixes and sorted SA12 suffixes
            for (int p = 0, t = n0 - n1, k = 0; k < n; k++) {
                int i = SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2; // pos of current offset 12 suffix
                int j = SA0[p]; // pos of current offset 0 suffix
                if (SA12[t] < n0 ? // different compares for mod 1 and mod 2 suffixes
                        leq(T[i], R[SA12[t] + n0], T[j], R[j / 3])
                        : leq(T[i], T[i + 1], R[SA12[t] - n0 + 1], T[j], T[j + 1],
                        R[j / 3 + n0])) { // suffix from SA12 is smaller
                    SA[k] = i;
                    if (++t == n02) // done --- only SA0 suffixes left
                        for (k++; p < n0; p++, k++) SA[k] = SA0[p];
                } else { // suffix from SA0 is smaller
                    SA[k] = j;
                    if (++p == n0) // done --- only SA12 suffixes left
                        for (k++; t < n02; t++, k++) SA[k] = SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2;
                }
            }
        }

        public static int[] suffixArray(CharSequence s) {
            int n = s.length();
            if (n <= 1)
                return new int[n];
            int[] S = IntStream.range(0, n + 3).map(i -> i < n ? s.charAt(i) : 0).toArray();
            int[] sa = new int[n];
            suffixArray(S, sa, n, 255);
            return sa;
        }

        public static int[] lcp(int[] sa, CharSequence s) {
            int n = sa.length;
            int[] rank = new int[n];
            for (int i = 0; i < n; i++) rank[sa[i]] = i;
            int[] lcp = new int[n - 1];
            for (int i = 0, h = 0; i < n; i++) {
                if (rank[i] < n - 1) {
                    for (int j = sa[rank[i] + 1]; Math.max(i, j) + h < s.length() && s.charAt(i + h) == s.charAt(j + h);
                         ++h)
                        ;
                    lcp[rank[i]] = h;
                    if (h > 0)
                        --h;
                }
            }
            return lcp;
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt(), k = in.nextInt();
            String s = in.next();
            if (n == 1) {
                out.println("YES");
                out.println(s);
                return;
            }
            int[] sa = suffixArray(s);
            int[] rank = new int[n];
            for (int i = 0; i < n; i++) rank[sa[i]] = i;
            int[] lcp = lcp(sa, s);
            ArrayList<Integer> positions = new ArrayList<>();
            TaskE.RmqSparseTable rmq = new TaskE.RmqSparseTable(lcp);
            for (int i = 0; i <= n - k; i++) positions.add(rank[i]);
            int[] ones = new int[n + 1];
            for (int i = n - 1; i >= 0; i--) {
                ones[i] = s.charAt(i) == '1' ? ones[i + 1] + 1 : 0;
            }
            int distinct = 1;
            Collections.sort(positions);
            for (int i = 1; i < positions.size(); i++) {
                if (rmq.min(positions.get(i - 1), positions.get(i) - 1) < k) distinct++;
            }
            if (k < 20 && (1 << k) == distinct) {
                out.println("NO");
                return;
            }
            out.println("YES");
            int K = k;
            while (k >= 20 || (1 << (k - 1)) > n) {
                out.print('0');
                k--;
            }
            ArrayList<Integer> P = new ArrayList<>();
            for (int j : positions) {
                int i = sa[j];
                if (ones[i] >= K - k) P.add(rank[i + K - k]);
            }
            for (; k > 0; k--) {
                int j = 0;
                while (j < P.size() && s.charAt(sa[P.get(j)]) == '0') j++;
                if (j == P.size()) {
                    for (int r = 0; r < k; r++) out.print('0');
                    out.println();
                    return;
                }
                distinct = 1;
                j++;
                for (; j < P.size(); j++) {
                    if (rmq.min(P.get(j - 1), P.get(j) - 1) < k) distinct++;
                }
                char c = distinct == (1 << (k - 1)) ? '1' : '0';
                out.print(c);
                positions.clear();
                for (int x : P) if (s.charAt(sa[x]) != c) positions.add(rank[sa[x] + 1]);
                P = new ArrayList<>(positions);
            }
            out.println();
        }

        static class RmqSparseTable {
            int[][] rmq;

            public RmqSparseTable(int[] a) {
                int n = a.length;
                rmq = new int[32 - Integer.numberOfLeadingZeros(n)][];
                rmq[0] = a.clone();
                for (int i = 1; i < rmq.length; i++) {
                    rmq[i] = new int[n - (1 << i) + 1];
                    for (int j = 0; j < rmq[i].length; j++)
                        rmq[i][j] = Math.min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
                }
            }

            public int min(int i, int j) {
                int k = 31 - Integer.numberOfLeadingZeros(j - i + 1);
                return Math.min(rmq[k][i], rmq[k][j - (1 << k) + 1]);
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
            writer.print('\n');
        }

        public void close() {
            writer.close();
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String next() {
            int c;
            while (isSpaceChar(c = this.read())) {
                ;
            }

            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);

            while (!isSpaceChar(c = this.read())) {
                result.appendCodePoint(c);
            }

            return result.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}