如果两个字符串 $$$a$$$ 和 $$$b$$$ (长度均为 $$$k$$$)在某个位置具有相同的字符,那么我们称它们有点相似,即。 e. [1, k]$$$ 中至少存在一个 $$$i 使得 $$$a_i = b_i$$$。
给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$(由 $$$n$$$ 字符 0 和/或 1 组成的字符串)和一个整数 $$$k$$$。我们将字符串 $$$s[i..j]$$$ 表示为 $$$s$$$ 的子字符串,从第 $$$i$$$ 个字符开始,到第 $$$j$$$ 个字符结束(即 $$$s[i..j] = s_i s_{i + 1} s_{i + 2} \dots s_{j - 1} s_j$$$)。
如果长度为 $$$k$$$ 的二进制字符串 $$$t$$$ 与长度恰好为 $$$k$$$ 的 $$$s$$$ 的所有子字符串有点相似,我们称其为漂亮;也就是说,它有点类似于 $$$s[1..k], s[2..k+1], \dots, s[n-k+1..n]$$$。
您的目标是找到按字典顺序排列的最小且漂亮的字符串 $$$t$$$,或者报告不存在这样的字符串。如果 $$$x$$$ 是 $$$y$$$ 的前缀(和 $$$x \ne y$$$),或者存在这样的 $$$i$$$ ($$$1 \le i \le \min(|x|, |y|)$$$),则字符串 $$$x$$$ 按字典顺序小于字符串 $$$y$$$,且 $$$x_i < y_i$$$,并且对于任何$$$j$$$ ($$$1 \le j < i$$$) $$$x_j = y_j$$$。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10000$$$) — 测试用例的数量。每个测试用例由两行组成。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10^6$$$)。第二行包含字符串 $$$s$$$,由 $$$n$$$ 个字符组成(每个字符为 0 或 1)。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,打印答案如下:
- 如果无法构造一个漂亮的字符串,则打印包含字符串 NO 的一行(注意:例如,完全大写,您不能打印 No);
- 否则,打印两行。第一行应包含字符串 YES(也是大写);第二行 — 按字典顺序排列的最小的漂亮字符串,由 $$$k$$$ 字符 0 和/或 1 组成。
示例
输入 #1
7 4 2 0110 4 2 1001 9 3 010001110 9 3 101110001 10 3 0101110001 10 10 1111111111 11 10 11111111110
输出 #1
YES 11 YES 00 YES 010 YES 101 NO YES 0000000001 YES 0000000010