Two Rectangles

Interview

Time limit2sMemory limit512 MB

Summary

Given a grid of black and white cells, decide whether the black cells form exactly two non-overlapping axis-aligned rectangles, and if so, label them with 'a' and 'b'.

Level: Medium6 of 10
Topics: Implementation, Brute force, Array, Geometry
Solved: No attempts yet

Problem

A famous abstract artist has just produced a new masterpiece, the painting <>. The painting is an $m\times n$ rectangle divided into $1\times 1$ squares, some of which are painted in the author's favorite color, black. Fedya is not a fan of abstract paintings, but he became curious whether the painting really depicts two non-overlapping rectangles. Help him find out. The rectangles do not overlap in the sense that they share no cells.

Input

The first line of the input file contains the numbers $m$ and $n$ ( $1 \le m, n \le 200$ ). The following $m$ lines contain a description of the picture. Each line contains exactly $n$ characters. The character <<.>> denotes an empty square, and the character <<#>> denotes a painted one.

Output

If the picture can be represented as two non-overlapping rectangles, print <<YES>> on the first line, and on the following $m$ lines print the picture in the same form as it was given in the input file, replacing the squares corresponding to the first rectangle with the character <<a>> and those of the second with the character <<b>>. If there are several solutions, print any of them.

If this cannot be done, print <<NO>> to the output file.

Examples5

Example 1

Input

4 6
.###..
.###..
...##.
......

Expected output

YES
.aaa..
.aaa..
...bb.
......

Example 2
Input
```
3 6
.###..
.####.
..###.
```
Expected output
```
NO
```

Example 3

Input

4 5
.####
.####
.####
.....

Expected output

YES
.abbb
.abbb
.abbb
.....

Example 4
Input
```
3 3
...
.#.
...
```
Expected output
```
NO
```
Example 5
Input
```
3 3
...
#.#
..#
```
Expected output
```
YES
...
b.a
..a
```