The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
J. Triminoes

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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.

Input

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.

Output

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.

Examples

Input

6 10

.w.wbw.wbw

wbwbw.w.w.

bw.wbwbwbw

w.wbw.wbwb

...wbw.w.w

..wbw.wbw.

Output

YES

.a.aaa.ccc

baccc.c.a.

ba.dddcbab

b.aaa.cbab

...bbb.b.b

..ccc.ddd.

Input

2 2

wb

bw

Output

NO

Input

1 3

wbw

Output

YES

bbb

Input

1 3

...

Output

YES

...

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2022 08:06:54 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|