给你一个 $$$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)$$$ 严格递增,即 $$$x_i < x_{i+1}$$$ 和 $$$y_i < y_{i+1}$$$ $$$1 \leq i < k$$$。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。以下行包含每个测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq k \leq n \leq 1000$$$)。
然后是 $$$n$$$ 行。第 $$$i$$$ 行包含长度为 $$$n$$$ 的二进制字符串 $$$s_i$$$。如果可以删除单元格 $$$(i, j)$$$,则 $$$s_i$$$ 的第 $$$j$$$ 个字符为 1,否则为 0。
保证所有测试用例的$$$n^2$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,如果无法精确删除 $$$(n-k+1)^2$$$ 单元格以满足条件,则输出“NO”(不带引号)。
否则,输出“YES”(不带引号)。然后,输出 $$$n$$$ 行。第 $$$i$$$ 行应包含长度为 $$$n$$$ 的二进制字符串 $$$t_i$$$。如果单元格 $$$(i, j)$$$ 被删除,则 $$$t_i$$$ 的第 $$$j$$$ 个字符为 0,否则为 1。
如果有多个解,则可以输出任意一个。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
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
输出 #1
YES 01 11 YES 0011 1111 1111 1100 NO YES 01111 11000 10000 10000 10000
注意
对于第一个测试用例,您只需删除单元格 $$$(1, 1)$$$。
对于第二个测试用例,您可以选择删除单元格 $$$(1,1)$$$、$$$(1,2)$$$、$$$(4,3)$$$ 和 $$$(4,4)$$$。
对于第三个测试用例,它不是解决方案,因为对角线中的单元格将始终形成长度 $$$5$$$ 的严格递增序列。