题目描述

一位巫毒女士曾经编织过一幅神奇的挂毯。

最初，她拿出一块空白画布。画布可以表示为一个 $r\times c$ 的网格，包含 $r$ 行、$c$ 列格子，因此共有

个网格点。

随后，她进行了若干次操作：沿网格线在画布上编织一条环。在同一条环中，每个网格点最多经过一次。此外，任意两条环都不能共享任何网格点。

最终，每个不在画布边界上的内部网格点，都恰好被一条环经过。内部网格点共有

个。

下面给出了 $r=2,c=3$ 时的若干种环的排列方式，灰色圆点表示内部网格点：

之后，她把画布放在地板上过夜。夜间，$r\cdot c$ 只绿色青蛙跳上画布，每个格子中恰好坐着一只青蛙。

接着，一位老巫婆来到画布旁，逐段扯掉所有编织线。每当她扯掉连接两个相邻网格点的一段编织线时，与该线段相邻的格子中的青蛙都会受到惊吓：

• 若线段位于画布边界，则有一只青蛙受到惊吓；
• 否则有两只青蛙受到惊吓。

每当青蛙受到惊吓时，它都会立即改变颜色：

• 绿色变为棕色；
• 棕色变为绿色。

若环按照上图排列，则最终青蛙颜色如下。灰色格子表示绿色青蛙，白色格子表示棕色青蛙：

当巫毒女士回到画布旁时，她只看到了两种颜色的青蛙，所有编织环都已经消失。

给定青蛙的最终颜色排列，请判断它是否可能由上述过程产生。如果可能，请恢复任意一种合法的环排列。

输入格式

每个输入包含多组测试数据。

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

对于每组测试数据：

• 第一行包含两个整数 $r,c$，表示网格的行数和列数；
• 接下来 $r$ 行，每行包含一个长度为 $c$ 的字符串，由字符 G 和 B 组成：
  • G 表示绿色青蛙；
  • B 表示棕色青蛙。

输出格式

对于每组测试数据：

• 若给定颜色排列不可能由上述过程产生，输出一行 NO；
• 否则先输出一行 YES，然后再输出 $2r+1$ 行二进制字符串，用来描述一种合法的编织线方案。

前 $r+1$ 行中的每一行长度均为 $c$，表示水平网格线段：

• 第 $i$ 行第 $j$ 个字符为 1，表示从上往下第 $i$ 条、从左往右第 $j$ 段水平网格线上有编织线；
• 为 0 则表示没有编织线。

接下来的 $r$ 行中的每一行长度均为 $c+1$，表示竖直网格线段：

• 第 $i$ 行第 $j$ 个字符为 1，表示从上往下第 $i$ 段、从左往右第 $j$ 条竖直网格线上有编织线；
• 为 0 则表示没有编织线。

样例

3
2 3
BBG
GBB
3 3
GGG
GGG
GGG
3 3
GGG
BBB
GGG

YES
001
101
100
0011
1100
YES
111
010
010
111
1001
1111
1001
NO

样例说明

第一组测试数据对应题目描述中第一种环排列。

在第二组测试数据中，样例输出对应下图左侧的方案。中间的方案同样合法；右侧的方案不合法，因为某些网格点被多于一条环共享。

完全不放置编织线同样不合法，因为内部网格点必须被一条环经过。

数据范围

所有测试数据中的 $r\cdot c$ 之和不超过 $2\cdot 10^6$。