G. Упоротое противодействие увеличению
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана таблица $$$n \times n$$$.

Обозначим за $$$(i, j)$$$ клетку из $$$i$$$-й строки и $$$j$$$-го столбца. Для каждой клетки известно, можно ее удалить или нет.

Дано целое число $$$k$$$, вам необходимо удалить ровно $$$(n-k+1)^2$$$ клеток из таблицы так, чтобы выполнялось следующее условие.

  • Нельзя найти $$$k$$$ неудаленных клеток $$$(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$$$ которые строго возрастают, т.е. $$$x_i < x_{i+1}$$$ и $$$y_i < y_{i+1}$$$ для всех $$$1 \leq i < k$$$.
Ваша задача найти любое решение, или сказать, что его нет.
Входные данные

В первой строк содержится целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборо входных данных.

Первая строка набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq k \leq n \leq 1000$$$).

Далее следуют $$$n$$$ строк. $$$i$$$-я строка содержит бинарную строку $$$s_i$$$ длины $$$n$$$. $$$j$$$-й символ $$$s_i$$$ это 1 если вы можете удалить клетку $$$(i, j)$$$, и 0 в противном случае.

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных, если не существует способа удалить ровно $$$(n-k+1)^2$$$ клеток, чтобы выполнить условие, выведите «NO» (без кавычек).

В противном случае выведите «YES» (без кавычек). Затем, выведите $$$n$$$ строк. $$$i$$$-я строка должна содержать бинарную строку $$$t_i$$$ длины $$$n$$$. $$$j$$$-й символ $$$t_i$$$ это 0 если клетка $$$(i, j)$$$ удалена, и 1 в противном случае.

Если существуют несколько решений, выведите любое из них.

Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes» и «Yes» будут распознаны как положительный ответ).

Пример
Входные данные
4
2 2
10
01
4 3
1110
0101
1010
0111
5 5
01111
10111
11011
11101
11110
5 2
10000
01111
01111
01111
01111
Выходные данные
YES
01
11
YES
0011
1111
1111
1100
NO
YES
01111
11000
10000
10000
10000
Примечание

В первом примере достаточно удалить клетку $$$(1, 1)$$$.

Во втором примере можно выбрать для удаления клетки $$$(1,1)$$$, $$$(1,2)$$$, $$$(4,3)$$$ и $$$(4,4)$$$.

Для третьего примера нет решения, потому что клетки по диагонали всегда будут образовывать строго возрастающую последовательность длины $$$5$$$.