Anti-Increasing Addicts
Description
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$.
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).
Input
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$.
Output
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).
Samples
<div class="test-example-line test-example-line-even test-example-line-0">4</div><div class="test-example-line test-example-line-odd test-example-line-1">2 2</div><div class="test-example-line test-example-line-odd test-example-line-1">10</div><div class="test-example-line test-example-line-odd test-example-line-1">01</div><div class="test-example-line test-example-line-even test-example-line-2">4 3</div><div class="test-example-line test-example-line-even test-example-line-2">1110</div><div class="test-example-line test-example-line-even test-example-line-2">0101</div><div class="test-example-line test-example-line-even test-example-line-2">1010</div><div class="test-example-line test-example-line-even test-example-line-2">0111</div><div class="test-example-line test-example-line-odd test-example-line-3">5 5</div><div class="test-example-line test-example-line-odd test-example-line-3">01111</div><div class="test-example-line test-example-line-odd test-example-line-3">10111</div><div class="test-example-line test-example-line-odd test-example-line-3">11011</div><div class="test-example-line test-example-line-odd test-example-line-3">11101</div><div class="test-example-line test-example-line-odd test-example-line-3">11110</div><div class="test-example-line test-example-line-even test-example-line-4">5 2</div><div class="test-example-line test-example-line-even test-example-line-4">10000</div><div class="test-example-line test-example-line-even test-example-line-4">01111</div><div class="test-example-line test-example-line-even test-example-line-4">01111</div><div class="test-example-line test-example-line-even test-example-line-4">01111</div><div class="test-example-line test-example-line-even test-example-line-4">01111</div>
YES
01
11
YES
0011
1111
1111
1100
NO
YES
01111
11000
10000
10000
10000
Note
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$.