题意：给定一个字符串s(1e6)，要求找出一个长为k(1e6)的字典序最小串s1使s1与s的每一个长为k的子串至少有一个位置相同；
枚举s的所有k长子串的反码，这n- k + 1个字符串是不能取的;当2^k大于n-k时，可将前个反码全设为0，枚举后个位置，最后取s子串反码没出现过的字典序最小串
#include<bits/stdc++.h>
using namespace std;const int N = (int)1e6 + 77;
int n, k;
bool ban[N];
char s[N];
int pref[N];void solve() {scanf("%d%d", &n, &k);scanf("%s", s);int m = 0;while (m < k && (1 << m) <= n) m++;for (int i = 0; i <= n && i < (1 << m); i++)ban[i] = false;pref[0] = 0;for (int i = 0; i < n; i++)pref[i + 1] = pref[i] + (int)(s[i] == '0');for (int l = 0; l + k <= n; l++) {if (pref[l] != pref[l + k - m]) continue;//前k-m个反码为全0int mask = 0;for (int i = 0; i < m; i++)if (s[l + k - 1 - i] == '0')mask ^= 1 << i;if (mask <= n) ban[mask] = 1;}int ans = 0;while (ans < (1 << m) && ban[ans]) ans++;if (ans == (1 << m)) {printf("NO\n");return;}printf("YES\n");for (int i = 0; i < k - m; i++)printf("0");for (int i = m - 1; i >= 0; i--)printf("%d", (ans >> i) & 1);printf("\n");
}int main()
{int t;scanf("%d", &t);while (t--) solve();return 0;
}