Anti-Increasing Addicts

2000ms

524288K

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

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

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

Sample Input:

Sample Output:

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

Informação

Provedor Codeforces

Código CF1738G