You are given a paired string s of length n (a line of n characters 0 and additionally 1) and an integer k. How about we indicate the string s[i..j] as the substring of s beginning from the I-th character and finishing with the j-th character (that is, s[i..j]=sisi+1si+2… sj−1sj). We should call a
Correct answer will be upvoted else Multiple Downvoted. Computer science.
You are given a paired string s of length n (a line of n characters 0 and additionally 1) and an integer k. How about we indicate the string s[i..j] as the substring of s beginning from the I-th character and finishing with the j-th character (that is, s[i..j]=sisi+1si+2… sj−1sj).
We should call a paired string t of length k wonderful in case it is somewhat like all substrings of s having length precisely k; that is, it is somewhat like s[1..k],s[2..k+1],… ,s[n−k+1..n].
You will likely find the lexicographically littlest string t that is lovely, or report that no such string exists. String x is lexicographically not as much as string y if either x is a prefix of y (and x≠y), or there exists such I (1≤i≤min(|x|,|y|)), that xi<yi, and for any j (1≤j<i) xj=yj.
Input
The main line contains one integer q (1≤q≤10000) — the number of experiments. Each experiment comprises of two lines.
The principal line of each experiment contains two integers n and k (1≤k≤n≤106). The subsequent line contains the string s, comprising of n characters (each character is either 0 or 1).
It is ensured that the amount of n over all experiments doesn't surpass 106.
Output
For each experiment, print the appropriate response as follows:
in case it is difficult to build a wonderful string, print one line containing the string NO (note: precisely in capitalized, you can't print No, for instance);
in any case, print two lines. The principal line ought to contain the string YES (precisely in capitalized also); the subsequent line — the lexicographically littlest excellent string, comprising of k characters 0 or potentially 1.
Step by step
Solved in 4 steps with 1 images
