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 \in [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} \dots 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], \dots, 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 \ne y$$$), or there exists such $$$i$$$ ($$$1 \le i \le \min(|x|, |y|)$$$), that $$$x_i < y_i$$$, and for any $$$j$$$ ($$$1 \le j < i$$$) $$$x_j = y_j$$$.
The first line contains one integer $$$q$$$ ($$$1 \le q \le 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 \le k \le n \le 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$$$.
For each test case, print the answer as follows:
7 4 2 0110 4 2 1001 9 3 010001110 9 3 101110001 10 3 0101110001 10 10 1111111111 11 10 11111111110
YES 11 YES 00 YES 010 YES 101 NO YES 0000000001 YES 0000000010
Name |
---|