CF44J.Triminoes

There are many interesting tasks on domino tilings. For example, an interesting fact is known. Let us take a standard chessboard (8 × 8) and cut exactly two squares out of it. It turns out that the resulting board can always be tiled using dominoes 1 × 2, if the two cut out squares are of the same color, otherwise it is impossible.

Petya grew bored with dominoes, that's why he took a chessboard (not necessarily 8 × 8), cut some squares out of it and tries to tile it using triminoes. Triminoes are reactangles 1 × 3 (or 3 × 1, because triminoes can be rotated freely), also the two extreme squares of a trimino are necessarily white and the square in the middle is black. The triminoes are allowed to put on the chessboard so that their squares matched the colors of the uncut squares of the chessboard, and also the colors must match: the black squares must be matched with the black ones only and the white ones — with the white squares. The triminoes must not protrude above the chessboard or overlap each other. All the uncut squares of the board must be covered with triminoes.

Help Petya find out if it is possible to tile his board using triminos in the described way and print one of the variants of tiling.

关于多米诺骨牌铺砌有许多有趣的题目。例如，一个有趣的事实是：取一个标准的国际象棋棋盘（$8 \times 8$），从中恰好挖去两个方格，则当且仅当被挖去的两个方格颜色相同时，剩余棋盘总能被 $1 \times 2$ 的多米诺骨牌完全铺满；否则无法铺满。

佩佳对多米诺骨牌感到厌倦，于是他取了一个棋盘（不一定是 $8 \times 8$），从中挖去了若干方格，并尝试用三格骨牌（trimino）来铺满它。三格骨牌是 $1 \times 3$ 或 $3 \times 1$ 的矩形（因三格骨牌可自由旋转），且其两端的方格必为白色，中间的方格必为黑色。允许将三格骨牌放置在棋盘上，使得其覆盖的方格颜色与未被挖去的棋盘方格颜色一致——即黑色方格只能覆盖棋盘上的黑色方格，白色方格只能覆盖棋盘上的白色方格。三格骨牌不得超出棋盘边界，也不得相互重叠。棋盘上所有未被挖去的方格都必须被三格骨牌完全覆盖。

请帮助佩佳判断：能否按上述方式用三格骨牌铺满他的棋盘？若可以，请输出一种可行的铺砌方案。

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) — the board size. Next n lines contain m symbols each and represent the board description. If some position contains ".", then the square in this position has been cut out. Symbol "w" stands for a white square, "b" stands for a black square. It is guaranteed that through adding the cut squares can result in a correct chessboard (i.e. with alternating black and white squares), thought, perhaps, of a non-standard size.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 1000$）——表示棋盘的尺寸。接下来的 $n$ 行，每行包含 $m$ 个字符，描述棋盘。若某位置为 .，则该位置的方格已被裁去；字符 w 表示白色方格，b 表示黑色方格。保证通过补上被裁去的方格，可以得到一个合法的国际象棋棋盘（即黑白方格交替排列），尽管其尺寸可能非标准。

If at least one correct tiling exists, in the first line print "YES" (without quotes), and then — the tiling description. The description must contain n lines, m symbols in each. The cut out squares, as well as in the input data, are marked by ".". To denote triminoes symbols "a", "b", "c", "d" can be used, and all the three squares of each trimino must be denoted by the same symbol. If two triminoes share a side, than they must be denoted by different symbols. Two triminoes not sharing a common side can be denoted by one and the same symbol (c.f. sample).

If there are multiple correct ways of tiling, it is allowed to print any. If it is impossible to tile the board using triminoes or the correct tiling, for which four symbols "a", "b", "c", "d" would be enough, doesn't exist, print "NO" (without quotes) in the first line.

如果至少存在一种正确的三格骨牌铺法，则在第一行输出 "YES"（不带引号），随后输出铺法描述。该描述需包含 $n$ 行，每行 $m$ 个字符。被挖去的方格（即输入中用 . 表示的方格）在输出中也需用 . 表示。三格骨牌可用字母 "a"、"b"、"c"、"d" 表示，且每个三格骨牌所占据的三个方格必须使用相同的字母。若两个三格骨牌有公共边，则它们必须用不同的字母表示；而两个不相邻（即无公共边）的三格骨牌可以使用相同的字母（参见样例）。

若存在多种正确的铺法，输出任意一种即可。若无法用三格骨牌铺满棋盘，或不存在仅需四种字母 "a"、"b"、"c"、"d" 即可完成的正确铺法，则在第一行输出 "NO"（不带引号）。