多米诺骨牌上有许多有趣的任务。例如,已知一个有趣的事实。让我们拿一个标准棋盘(8 × 8)并从中切出两个正方形。事实证明,如果两个切出的方块颜色相同,则所得的板总是可以使用多米诺骨牌 1 × 2 进行平铺,否则这是不可能的。
Petya 对多米诺骨牌感到厌倦,这就是为什么他拿了一个棋盘(不一定是 8 × 8),从中切出一些正方形,并尝试用三米诺骨牌将其平铺。三联体是 1 × 3 的反应角(或 3 × 1,因为三联体可以自由旋转),而且三联体的两个极端正方形必然是白色,中间的正方形是黑色。允许将三边形放在棋盘上,使其方块与棋盘上未切割方块的颜色相匹配,并且颜色也必须匹配:黑色方块必须仅与黑色方块匹配,白色方块必须与白色方块匹配。三分骨不得突出棋盘上方或相互重叠。板上所有未切割的方块都必须用三米诺覆盖。
帮助 Petya 找出是否可以按照所描述的方式使用 triminos 来平铺他的板,并打印平铺的一种变体。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000) — 棋盘尺寸。接下来的 n 行每行包含 m 个符号,代表板的描述。如果某个位置包含“.”,则说明该位置的方块已被切掉。符号“w”代表白色方块,“b”代表黑色方块。可以保证,通过添加切割的方块可以产生正确的棋盘(即具有交替的黑色和白色方块),也许可以认为是非标准尺寸。
输出
如果至少存在一个正确的平铺,则在第一行打印“YES”(不带引号),然后 — 平铺描述。描述必须包含 n 行,每行 m 个符号。剪下的方块以及输入数据中的方块都用“.”标记。为了表示三分音符号,可以使用“a”、“b”、“c”、“d”,并且每个三分音的所有三个方块必须用相同的符号表示。如果两个三米诺共用一条边,则它们必须用不同的符号表示。不共享公共边的两个三米诺可以用一个相同的符号表示(参见示例)。
如果有多种正确的平铺方式,则允许打印任何一种。如果无法使用 triminoes 平铺棋盘或正确的平铺(对于四个符号“a”、“b”、“c”、“d”就足够了,但不存在),请在第一行打印“NO”(不带引号)。
示例
输入 #1
6 10 .w.wbw.wbw wbwbw.w.w. bw.wbwbwbw w.wbw.wbwb ...wbw.w.w ..wbw.wbw.
输出 #1
YES .a.aaa.ccc baccc.c.a. ba.dddcbab b.aaa.cbab ...bbb.b.b ..ccc.ddd.
输入 #2
2 2 wb bw
输出 #2
NO
输入 #3
1 3 wbw
输出 #3
YES bbb
输入#4
1 3 ...
输出#4
YES ...