E. Немного похожи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Назовем две строки $$$a$$$ и $$$b$$$ (обе длиной $$$k$$$) немного похожими, если они имеют один и тот же символ в некоторой позиции, то есть существует по крайней мере одно $$$i \in [1, k]$$$ такое, что $$$a_i = b_i$$$.

Задана двоичная строка $$$s$$$ длины $$$n$$$ (строка из $$$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$$$).

Назовем двоичную строку $$$t$$$ длины $$$k$$$ красивой, если она немного похожа на все подстроки $$$s$$$, имеющие длину ровно $$$k$$$; то есть она немного похожа на $$$s[1..k], s[2..k+1], \dots, s[n-k+1..n]$$$.

Ваша задача — найти лексикографически наименьшую строку $$$t$$$, которая является красивой, или сообщить, что такой строки не существует. Строка $$$x$$$ лексикографически меньше строки $$$y$$$, если $$$x$$$ является префиксом $$$y$$$ (и $$$x \ne y$$$), либо существует такое $$$i$$$ ($$$1 \le i \le \min(|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.
Пример
Входные данные
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