题目背景

本题目来自仓库 https://github.com/Disposrestfully/CCPC-CQ-2024/tree/main

题目描述

给定正整数 $n$ 和两个仅包含字符 . 和 # 的长度为 $n$ 的字符串 $a, b$，请构造一个 $7\times n$ 的仅包含字符 . 与 # 的矩阵，满足以下条件：

• 矩阵第 $1$ 行与 $a$ 相同，第 $7$ 行与 $b$ 相同。
• 由四方向连通的 # 构成的图形均为实心的矩形。具体地：
  • 对于两个 # 字符，如果可以从其中一个 # 字符出发，在有限步之内仅经过 # 字符到达另一个 # 字符，其中每一步均为向上、左、下、右四个方向之一移动一格，则称这两个 # 字符在同一组。那么，由同一组内的所有 # 字符构成的图形均为实心的矩形。
• 所有的 # 字符八方向连通，具体地：
  • 对于任意两个 # 字符，均可以从其中一个 # 字符出发，在有限步之内仅经过 # 字符到达另一个 # 字符，其中每一步均为向上、左、下、右、左上、右上、左下、右下八个方向之一移动一格。

请输出任意一个满足条件的矩阵，或判定无解。

输入格式

输入的第一行包含一个正整数 $T \ (1\le T \le 10^4)$，代表数据组数。

每组数据第一行包含一个正整数 $n \ (2\le n \le 10^5)$，代表矩阵的宽度。

接下来两行分别包含仅包含字符 . 与 #，长度为 $n$ 的两个字符串 $a, b$，代表矩阵的第 $1$ 行与第 $7$ 行。

保证 $a$ 与 $b$ 均包含至少一个 #。

保证单个测试点内所有 $n$ 的总和不超过 $2\times10^5$。

输出格式

对于每组测试数据，如果不存在满足要求的矩阵，则输出一行一个字符串 No。

如果存在满足要求的矩阵，则先输出一行一个字符串 Yes，然后输出 $7$ 行，每行包含一个长度为 $n$ 的字符串，代表你构造的矩阵。

4
4
#..#
.##.
5
##.#.
.#.##
6
######
.####.
27
.######.######.####.#.#####
.####...####..#.......#####

Yes
#..#
.##.
.##.
#..#
.##.
.##.
.##.
Yes
##.#.
##.#.
##.#.
..#..
.#.##
.#.##
.#.##
No
Yes
.######.######.####.#.#####
#......#......#....#.#.....
#......#......#....#.#.....
#......#.......####..#.....
#......#......#......#.....
#......#......#......#.....
.####...####..#.......#####

提示

对于第一组数据，以下是另一种正确答案：

#..#
#..#
#..#
.##.
#..#
#..#
.##.

但以下矩阵不是正确答案，因为由 $(1,1)(2,1)(2,2)$ 这组四方向连通的 # 字符构成的图形不是矩形。对于 $(4,1)(4,2)(5,1)(6,1)$ 这组四方向连通的 # 字符同理。

#..#
##.#
..#.
##.#
#.#.
#..#
.##.

同样，以下矩阵也不是正确答案，因为位于 $(1,1)$ 的 # 字符与其他 # 字符不满足八方向连通的条件。

#..#
...#
...#
...#
...#
...#
.##.