CF1738G.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 \lt x_{i+1}$ and $y_i \lt y_{i+1}$ for all $1 \leq i \lt k$.

Your task is to find a solution, or report that it is impossible.

给你一个 $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)$，它们是严格递增的，即对所有 $1 \leq i < k$，均有 $x_i < x_{i+1}$ 且 $y_i < y_{i+1}$。

你的任务是找出一种可行方案，或判定其不可能。

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来的若干行描述每个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq k \leq n \leq 1000$）。

随后是 $n$ 行。第 $i$ 行包含一个长度为 $n$ 的二进制字符串 $s_i$。$s_i$ 的第 $j$ 个字符为 1 表示可以删除单元格 $(i, j)$，为 0 表示不可删除。

保证所有测试用例中 $n^2$ 的总和不超过 $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).

对于每个测试用例，若不存在恰好删除 $(n-k+1)^2$ 个格子以满足条件的方法，则输出 "NO"（不带引号）。

否则，输出 "YES"（不带引号）。然后，输出 $n$ 行。第 $i$ 行应包含一个长度为 $n$ 的二进制字符串 $t_i$。其中 $t_i$ 的第 $j$ 个字符为 0 表示格子 $(i, j)$ 被删除，为 1 表示未被删除。

若存在多种解法，输出任意一种即可。

"YES" 和 "NO" 的大小写不限（例如，字符串 "yEs"、"yes" 和 "Yes" 均会被识别为肯定回答）。

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

对于第一个测试用例，你只需删除单元格 $(1, 1)$。

对于第二个测试用例，你可以选择删除单元格 $(1,1)$、$(1,2)$、$(4,3)$ 和 $(4,4)$。

对于第三个测试用例，不存在解，因为对角线上的单元格将始终构成一个长度为 $5$ 的严格递增序列。