Monocarp 正在玩 Minecraft,想要建造一堵仙人掌墙。他想将其建造在一块大小为 $$$n \times m$$$ 个单元格的沙地上。最初,田野的一些小区里有仙人掌。请注意,在 Minecraft 中,仙人掌不能在彼此相邻的单元格上生长 - 并且初始字段满足此限制。 Monocarp可以种植新的仙人掌(它们也必须满足上述条件)。他无法砍倒地里已经长出的任何仙人掌——他没有斧子,而且仙人掌对他的手来说太刺了。
Monocarp 认为,如果没有从场地顶行到底行的路径,则墙是完整的,这样:
- 路径中每两个连续的单元格相邻;
- 属于该路径的单元格不包含仙人掌。
你的任务是种植最少数量的仙人掌来建造一堵墙(或者报告这是不可能的)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$; $$$n \times m \le 4 \cdot 10^5$$$) - 分别是行数和列数。
接下来是 $$$n$$$ 行,如果仙人掌生长在第 $$$i$$$ 行和第 $$$j$$$ 列的交叉处,则 $$$i$$$ 行包含长度为 $$$m$$$ 的字符串 $$$s_i$$$,其中 $$$s_{i, j}$$$ 为“#”。否则,$$$s_{i, j}$$$ 为“.”。
所有测试用例的 $$$n \times m$$$ 总和不超过 $$$4 \cdot 10^5$$$。
输出
对于每个测试用例,如果不可能在不违反规则的情况下建造仙人掌墙,请在第一行打印“NO”。否则,在第一行打印 YES,然后打印 $$$n$$$ 行,每行包含 $$$m$$$ 个字符 — 字段本身,其中第 $$$i$$$ 行的第 $$$j$$$ 字符等于“#”,如果第 $$$i$$$ 行和第 $$$j$$$ 列的交叉点上有仙人掌,否则为“.”。如果有多个最佳答案,请打印其中任何一个。
示例
输入 #1
4 2 4 .#.. ..#. 3 3 #.# ... .#. 5 5 ..... ..... ..... ..... ..... 4 3 #.. .#. #.# ...
输出 #1
YES .#.# #.#. NO YES ....# ...#. ..#.. .#... #.... YES #.. .#. #.# ...