Anti-Increasing Addicts

有 $n\times n$ 的方格，给定每个方格可否被删除。 给定整数 $k$ ，要求删除 $(n-k+1)^2$ 个方格，使得不存在 $k$ 个严格单调递增（横纵坐标均严格单调递增）的方格未被删除或证明其无解。 输入第一行一个整数 $t$，表示测试数据组数。 以下每组第一行两个整数 $n,k$ 满足 $2\le n, k\le 1000$ ，以下 $n$ 行，每行 $n$ 个数字， $1$ 表示可删除该方格， $0$ 反之。 保证所有数据中 $n^2$ 的和不超过 $10^6$ 。 对于每组测试数据，若有解，输出 `YES` 并输出 $n$ 行，每行 $n$ 个数字， $0$ 表示该方格被删除， $1$ 反之。仅需输出任一个解。若无解输出 `NO`。不考虑大小写。 对于第一组数据，只需要删除 $(1,1)$。对于第二组数据，可以删除 $(1,1),(1, 2),(4, 3),(4,4)$。对于第三组数据，没有解。

You are given an $ n \times n $ grid. We write $ (i, j) $ to denote the cell in the $ i $ -th row and $ j $ -th column. For each cell, you are told whether yon can delete it or not. Given an integer $ k $ , you are asked to delete exactly $ (n-k+1)^2 $ cells from the grid such that the following condition holds. - You cannot find $ k $ not deleted cells $ (x_1, y_1), (x_2, y_2), \dots, (x_k, y_k) $ that are strictly increasing, i.e., $ x_i < x_{i+1} $ and $ y_i < y_{i+1} $ for all $ 1 \leq i < k $ . Your task is to find a solution, or report that it is impossible.

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The following lines contain the description of each test case. The first line of each test case contains two integers $ n $ and $ k $ ( $ 2 \leq k \leq n \leq 1000 $ ). Then $ n $ lines follow. The $ i $ -th line contains a binary string $ s_i $ of length $ n $ . The $ j $ -th character of $ s_i $ is 1 if you can delete cell $ (i, j) $ , and 0 otherwise. It's guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 10^6 $ .

For each test case, if there is no way to delete exactly $ (n-k+1)^2 $ cells to meet the condition, output "NO" (without quotes). Otherwise, output "YES" (without quotes). Then, output $ n $ lines. The $ i $ -th line should contain a binary string $ t_i $ of length $ n $ . The $ j $ -th character of $ t_i $ is 0 if cell $ (i, j) $ is deleted, and 1 otherwise. If there are multiple solutions, you can output any of them. You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

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

For the first test case, you only have to delete cell $ (1, 1) $ . For the second test case, you could choose to delete cells $ (1,1) $ , $ (1,2) $ , $ (4,3) $ and $ (4,4) $ . For the third test case, it is no solution because the cells in the diagonal will always form a strictly increasing sequence of length $ 5 $ .