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 CPP):

Solution:
#define _USE_MATH_DEFINES
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX

#include <bits/stdc++.h>
using namespace std;

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

#define OPEN(a) freopen(a, "r", stdin)
#define F first
#define S second
#define PB push_back
#define BOOST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ALL(i) begin((i)), end((i))
#define SZ(i) ((int)i.size())
#define SORT(a) sort(ALL(a))

using LL = long long;
using LD = long double;//__float128;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;
using VI = vector<int>;
using VLL = vector<LL>;
using VLD = vector<LD>;
using VPII = vector<PII>;
using VPLL = vector<PLL>;
using VPLD = vector<PLD>;
using VVI = vector<VI>;

#define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME
#define __FOR3(i, a, n, inc) for(int i = (a); (inc) > 0 ? i < (n) : i >= (n); i += (inc))
#define __FOR2(i, a, n) __FOR3(i, a, n, 1)
#define __FOR1(i, n) __FOR2(i, 0, n)
#define FOR(...) GET_MACRO(__VA_ARGS__, __FOR3, __FOR2, __FOR1)(__VA_ARGS__)

#define REV(a,b) for(int a= b; a >= 0; --a)
#define FRU(a,b) for(const auto& a: b)
#define FRUM(a,b) for(auto& a : b)

const int inf = 1e9 + 7;
const int MOD = inf;
const LL INF = 1e18 + 7;
const long double PI = acos(-1);
const LD EPS = 1e-9;


namespace input {
    template< class T> istream& operator>>(istream& st, vector<T> & container) { for (auto& u : container) st >> u; return st; }
    template< class T, size_t N> istream& operator>>(istream& st, array<T, N> & container) { for (auto& u : container) st >> u; return st; }
    template <class T, class U> istream& operator>>(istream& st, pair<T, U> & p) { st >> p.first >> p.second; return st; }

    void re() {}
    template<typename T, typename... TArgs> void re(T& x, TArgs&... rest) { cin >> x; re(rest...); }
}
using namespace input;


namespace output
{
    template< class T> ostream& operator<<(ostream& st, const vector<T> & container) { for (auto& u : container) st << u << ' '; return st; }
    template< class T> ostream& operator<<(ostream& st, const deque<T> & container) { for (auto& u : container) st << u << ' '; return st; }
    template< class T, size_t N> ostream& operator<<(ostream& st, const array<T, N> & container) { for (auto& u : container) st << u << ' '; return st; }
    template <class T, class U> ostream& operator<<(ostream& st, pair<T, U> p) { st << p.first << ' ' << p.second; return st; }

    void pr() {}
    template <typename T> void pr(const T& x) { cout << x; }
    template <typename T, typename... TArgs> void pr(const T& x, const TArgs&... rest) { cout << x << ' '; pr(rest...); }
    template <typename... TArgs> void prln(const TArgs&... args) { pr(args...); cout << '\n'; }
}
using namespace output;

namespace pairs
{
    template<class T, class U, class V> pair<T, U> operator* (pair<T, U>p, V val) { return{ p.first * val, p.second * val }; }
    template<class T, class U, class V> pair<T, U> operator/ (pair<T, U>p, V val) { return{ p.first / val, p.second / val }; }
    template<class T, class U>  pair<T, U> operator- (pair<T, U> a, pair<T, U> b) { return{ a.first - b.first, a.second - b.second }; }
    template<class T, class U>  pair<T, U> operator+ (pair<T, U> a, pair<T, U> b) { return{ a.first + b.first, a.second + b.second }; }
}
using namespace pairs;

namespace triples
{
#define TT1T2T3 template<class T1, class T2, class T3>
#define TT1T2T3T4 template<class T1, class T2, class T3, class T4>
#define TRT1T2T3  triple<T1, T2, T3>
    TT1T2T3 struct triple { T1 x; T2 y; T3 z; triple() : x(T1()), y(T2()), z(T3()) {};
     triple(T1 _x, T2 _y, T3 _z) :x(_x), y(_y), z(_z) {} };
    TT1T2T3 bool operator<(const TRT1T2T3&t1, const TRT1T2T3&t2) { if (t1.x != t2.x)return t1.x < t2.x; if (t1.y != t2.y) return t1.y < t2.y; else return t1.z < t2.z; }
    TT1T2T3 bool operator>(const TRT1T2T3&t1, const TRT1T2T3&t2) { if (t1.x != t2.x)return t1.x > t2.x; if (t1.y != t2.y) return t1.y > t2.y; else return t1.z > t2.z; }
    TT1T2T3 bool operator==(const TRT1T2T3&t1, const TRT1T2T3&t2) { return (t1.x == t2.x && t1.y == t2.y && t1.z == t2.z); }
    TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.x >> t.y >> t.z; }
    TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t) { return os << t.x << " " << t.y << " " << t.z; }

    TT1T2T3 TRT1T2T3 operator+(TRT1T2T3 a, TRT1T2T3 b) { return { a.x + b.x, a.y + b.y, a.z + b.z }; }
    TT1T2T3 TRT1T2T3 operator-(TRT1T2T3 a, TRT1T2T3 b) { return { a.x - b.x, a.y - b.y, a.z - b.z }; }
    TT1T2T3T4 TRT1T2T3 operator*(TRT1T2T3 a, T4 val) { return { a.x * val, a.y * val, a.z * val }; }
    TT1T2T3T4 TRT1T2T3 operator/(TRT1T2T3 a, T4 val) { return { a.x / val, a.y / val, a.z / val }; }

#undef TT1T2T3T4
#undef TRT1T2T3
#undef TT1T2T3
    using TRII = triple<int, int, int>;
    using TRLL = triple<LL, LL, LL>;
    using TRLD = triple<LD, LD, LD>;
    using VTRII = vector<TRII>;
    using VTRLL = vector<TRLL>;
    using VTRLD = vector<TRLD>;
}
using namespace triples;

namespace geo
{
    template<class T> T dotProduct(pair<T, T> a, pair<T, T> b) { return a.first*b.first + a.second* b.second; }
    template<class T> T crossProduct(pair<T, T>a, pair<T, T> b) { return a.first * b.second - a.second * b.first; }
    template<class T> T lengthPow(pair<T, T> a) { return a.first*1ll*a.first + a.second*1ll*a.second; }
    template<class T> LD length(pair<T, T> a) { return sqrt(lengthPow(a)); }


    template<class T> T dotProduct(triple<T, T, T> a, triple<T, T, T> b) { return a.x*b.x + a.y* b.y + a.z*b.z; }
    template<class T> T crossProduct(triple<T, T, T> a, triple<T, T, T> b) { return { a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x }; }
    template<class T> T lengthPow(triple<T, T, T> a) { return a.x*1ll*a.x + a.y*1ll*a.y + a.z*1ll*a.z; }
    template<class T> LD length(triple<T, T, T> a) { return sqrt(lengthPow(a)); }
}
using namespace geo;

template <class T> T invGeneral(T a, T b) { // 0 < a < b, gcd(a,b) = 1
    a %= b;
    if (a == 0) return b == 1 ? 0 : -1;
    T x = invGeneral(b, a);
    return x == -1 ? -1 : ((1 - (LL)b * x) / a + b) % b;
}

template<class T> struct modular {
    T val;
    explicit operator T() const { return val; }
    modular() { val = 0; }
    modular(const LL& v) {
        val = (-MOD <= v && v <= MOD) ? v : v % MOD;
        if (val < 0) val += MOD;
    }

    friend ostream& operator<<(ostream& os, const modular& a) { return os << a.val; }
    friend void pr(const modular& a) { pr(a.val); }
    friend void re(modular& a) { LL x; re(x); a = modular(x); }

    friend bool operator==(const modular& a, const modular& b) { return a.val == b.val; }
    friend bool operator!=(const modular& a, const modular& b) { return !(a == b); }
    friend bool operator<(const modular& a, const modular& b) { return a.val < b.val; }

    modular operator-() const { return modular(-val); }
    modular& operator+=(const modular& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
    modular& operator-=(const modular& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
    modular& operator*=(const modular& m) { val = (LL)val*m.val%MOD; return *this; }
    friend modular pow(modular a, LL p) {
        modular ans = 1; for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
        return ans;
    }
    friend modular inv(const modular& a) {
        auto i = invGeneral(a.val, MOD); assert(i != -1);
        return i;
    } // equivalent to return exp(b,MOD-2) if MOD is prime
    modular& operator/=(const modular& m) { return (*this) *= inv(m); }

    friend modular operator+(modular a, const modular& b) { return a += b; }
    friend modular operator-(modular a, const modular& b) { return a -= b; }
    friend modular operator*(modular a, const modular& b) { return a *= b; }
    friend modular operator/(modular a, const modular& b) { return a /= b; }
};

using MI = modular<int>;
using PMI = pair<MI, MI>;
using VMI = vector<MI>;
using VPMI = vector<PMI>;


namespace debug {
    template < typename _T > inline void _debug(const char *s, _T x) { cerr << s << " = " << x << "\n"; }
    template < typename _T, typename... args > void _debug(const char *s, _T x, args... a) { while (*s != ',') cerr << *s++; cerr << " = " << x << ','; _debug(s + 1, a...); }

#if 1 && defined(LOCAL)
#define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 1999
#define cerr if(0) cout
#endif
}
using namespace debug;

template <class T> bool setMax(T& v, T newV) { if (v < newV) { v = newV; return true; } return false; }
template <class T> bool setMin(T& v, T newV) { if (v > newV) { v = newV; return true; } return false; }

string s;
string res;

pair<VI,VI> split(const VI & dane, int pos)
{
    VI zer, jed;

    for(auto u : dane)
    {
        if(s[u + pos] == '0')
            zer.push_back(u);
        else
            jed.push_back(u);
    }
    return {zer, jed};
}

bool calc(int i, int k, const VI & potrzebne)
{
    if(i == k)
    {
        return potrzebne.size() == 0;
    }

    auto [zer, jed] = split(potrzebne, i);
    res += '0';
    if(calc(i + 1, k, jed))
    {
        return true;
    }
    else
    {
        res.back() = '1';
        if(calc(i + 1, k, zer))
        {
            return true;
        }
        res.pop_back();
        return false;
    }
}

void solve()
{
    int n, k;
    re(n, k);

    re(s);


    int ile = n - k + 1;
    // if(k < 30 and ile >= (1 << k))
    // {
    //     prln("NO");
    //     return;
    // }


    ile = max(0, k - 25);
    res = string(ile, '0');

    VI potrzebne;

    deque<int> zera;
    FOR(i, ile)
    {
        if(s[i] == '0')
            zera.push_back(i);
    }
    FOR(i, ile, n)
    {
        int id = i - ile;
        if(id + k  > n)
            break;
        while(zera.size() and zera.front() < id)
            zera.pop_front();

        if(zera.empty())
            potrzebne.push_back(id);
        
        if(s[i] == '0')
            zera.push_back(i);
    
    }

    auto ok = calc(ile, k, potrzebne);

    if(not ok)
    {
        prln("NO");
        return;
    }
    



    prln("YES");
    prln(res);

}

int main()
{   
    // #ifndef LOCAL
        // freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
    // #endif
    BOOST;
    cout << fixed << setprecision(13);
    int t = 1;
    cerr << "testy!!!!\n"; cin >> t;
    for(int i = 1; i <= t; ++i)
    // string s;
    // while(cin >> s)
    {
        solve();
    }
    return 0;
}