J. Триминошки
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Бывает много интересных задач о замощении доминошками. Например, известен такой замечательный факт. Возьмем стандартную шахматную доску (8 × 8) и вырежем из нее ровно две клетки. Оказывается, что получившуюся доску всегда можно замостить доминошками 1 × 2, если две вырезанные клетки разного цвета, и нельзя в противном случае.

Пете наскучили доминошки, поэтому он взял шахматную доску (не обязательно 8 × 8), вырезал из нее некоторые клетки и пытается замостить ее триминошками. Триминошки — это прямоугольники 1 × 3 (или 3 × 1, потому что триминошки можно беспрепятственно поворачивать), причем две крайние клетки триминошки обязательно белые, а клетка в середине — черная. Триминошки разрешается класть на шахматную доску таким образом, чтобы их клетки совпадали с невырезанными клетками доски, причем должно выполняться соответствие цветов: черные клетки можно совмещать только с черными, а белые — с белыми. Триминошки не должны выступать за пределы доски или накладываться друг на друга. Все невырезанные клетки доски должны быть покрыты триминошками.

Помогите Пете определить, можно ли замостить его доску триминошками описанным способом и выведите один из вариантов замощения.

Входные данные

В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 1000) — размеры доски. Следующие n строк содержат по m символов каждая и представляют собой описание доски. Если в некоторой позиции содержится «.», то клетка в этой позиции вырезана. Белой клетке соответствует символ «w», черной — «b». Гарантируется, что путем добавления вырезанных клеток можно получить корректную шахматную доску (т.е. с чередованием черных и белых клеток), хотя, возможно, и нестандартного размера.

Выходные данные

Если хотя бы одно корректное замощение существует, выведите в первой строке «YES» (без кавычек), а затем — описание замощения. Описание должно содержать n строк, по m символов в каждой. Вырезанные клетки, как и во входных данных, обозначаются символом «.». Для обозначения триминошек можно использовать символы «a», «b», «c», «d», причем все три клетки каждой триминошки должны обозначаться одним символом. Если две триминошки граничат по стороне, то они должны обозначаться разными символами. Две триминошки, не граничащие по стороне, могут обозначаться одним и тем же символом (см. пример).

Если корректных замощений несколько, разрешается выводить любое. Если замостить доску триминошками невозможно или не существует корректного замощения, для описания которого было бы достаточно четырех символов «a», «b», «c», «d», выведите в первой строке «NO» (без кавычек).

Примеры
Входные данные
6 10
.w.wbw.wbw
wbwbw.w.w.
bw.wbwbwbw
w.wbw.wbwb
...wbw.w.w
..wbw.wbw.
Выходные данные
YES
.a.aaa.ccc
baccc.c.a.
ba.dddcbab
b.aaa.cbab
...bbb.b.b
..ccc.ddd.
Входные данные
2 2
wb
bw
Выходные данные
NO
Входные данные
1 3
wbw
Выходные данные
YES
bbb
Входные данные
1 3
...
Выходные данные
YES
...