反递增爱好者

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一个 $n\times n$ 的网格。用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子。输入会说明每个格子是否允许删除。

你需要恰好删除 $(n-k+1)^2$ 个格子，使未删除的格子中不存在长度为 $k$ 的严格递增序列。也就是说，不能找到

使得对每个 $1\le i<k$ 都有 $x_i<x_{i+1}$ 且 $y_i<y_{i+1}$。

请输出任意一种合法删除方案；若不存在，输出无解。

输入格式

第一行一个整数 $t$，表示测试数据组数。

每组数据的第一行包含两个整数 $n,k$。随后 $n$ 行，每行一个长度为 $n$ 的二进制串 $s_i$：

• $s_{i,j}=1$ 表示格子 $(i,j)$ 允许删除；
• $s_{i,j}=0$ 表示格子 $(i,j)$ 必须保留。

输出格式

对每组数据：

• 若无解，输出一行 NO；
• 否则输出一行 YES，再输出 $n$ 行长度为 $n$ 的二进制串。输出串中的 0 表示删除该格子，1 表示保留该格子。

YES 与 NO 不区分大小写。

样例输入

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

数据范围

对所有数据，$1\le t\le10^5$，$2\le k\le n\le1000$，且所有测试数据中 $n^2$ 的总和不超过 $10^6$。

说明

输出中的 0 必须对应输入中允许删除的格子，并且每组数据必须恰好输出 $(n-k+1)^2$ 个 0。

本题为多解构造题，评测器会直接验证输出方案，不要求与样例输出相同。