A15415. Anti-Increasing Addicts

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).

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$ .