Бывает много интересных задач о замощении доминошками. Например, известен такой замечательный факт. Возьмем стандартную шахматную доску (8 × 8) и вырежем из нее ровно две клетки. Оказывается, что получившуюся доску всегда можно замостить доминошками 1 × 2, если две вырезанные клетки разного цвета, и нельзя в противном случае.
Пете наскучили доминошки, поэтому он взял шахматную доску (не обязательно 8 × 8), вырезал из нее некоторые клетки и пытается замостить ее триминошками. Триминошки — это прямоугольники 1 × 3 (или 3 × 1, потому что триминошки можно беспрепятственно поворачивать), причем две крайние клетки триминошки обязательно белые, а клетка в середине — черная. Триминошки разрешается класть на шахматную доску таким образом, чтобы их клетки совпадали с невырезанными клетками доски, причем должно выполняться соответствие цветов: черные клетки можно совмещать только с черными, а белые — с белыми. Триминошки не должны выступать за пределы доски или накладываться друг на друга. Все невырезанные клетки доски должны быть покрыты триминошками.
Помогите Пете определить, можно ли замостить его доску триминошками описанным способом и выведите один из вариантов замощения.
Выходные данные
Если хотя бы одно корректное замощение существует, выведите в первой строке «YES» (без кавычек), а затем — описание замощения. Описание должно содержать n строк, по m символов в каждой. Вырезанные клетки, как и во входных данных, обозначаются символом «.». Для обозначения триминошек можно использовать символы «a», «b», «c», «d», причем все три клетки каждой триминошки должны обозначаться одним символом. Если две триминошки граничат по стороне, то они должны обозначаться разными символами. Две триминошки, не граничащие по стороне, могут обозначаться одним и тем же символом (см. пример).
Если корректных замощений несколько, разрешается выводить любое. Если замостить доску триминошками невозможно или не существует корректного замощения, для описания которого было бы достаточно четырех символов «a», «b», «c», «d», выведите в первой строке «NO» (без кавычек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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 2
wb
bw
|
NO
|
|
3
|
1 3
wbw
|
YES
bbb
|
|
4
|
1 3
...
|
YES
...
|