Доктор Ливси очень любит ходить, но, к сожалению, недавно он сломал ногу. Поэтому сегодня он будет ходить в настольной игре «Шашматы», в которую играет против Билли Бонса.
Билли выставляет на поле размера $$$8 \times 8$$$ одну белую шашку и $$$n$$$ чёрных шашек. Ливси играет за белых и ходит первым. Победить Билли можно только в одном случае: если за один ход побить все чёрные шашки.
Как бьёт шашка? Шашка может побить шашку, если та стоит на следующей клетке по диагонали в любом из четырёх направлений, и следующая клетка в этом направлении после неё существует и свободна. Чтобы побить её, нам нужно поставить свою шашку на следующую клетку после той шашки, которую мы бьём. При этом побитая шашка сразу снимается с поля, а наша шашка может продолжить ход.
Также белая шашка может быть дамкой.
Как шашка может стать дамкой? Шашка может либо изначально быть дамкой, либо превратиться в неё, как только достигнет одной из четырёх границ поля.
Как бьёт дамка? Дамка, в отличие от обычной шашки, может бить в любом из восьми направлений — по вертикали, горизонтали и диагонали — и перемещаться при этом на любое количество клеток. Для того, чтобы шашку можно было бить, между начальной и конечной позициями дамки должна быть ровно одна эта шашка и любое количество пустых клеток. Побитая шашка сразу снимается с поля, а дамка может продолжить ход.
Вам дано описание игрового поля размера $$$8 \times 8$$$. На нём стоят $$$n$$$ ($$$1 \le n \le 15$$$) чёрных шашек и одна белая шашка.
Если Доктор Ливси сможет обыграть Билли Бонса, то выведите выигрышную последовательность ходов. Если таких последовательностей несколько, то выведите самую длинную, ведь Доктор Ливси очень любит ходить. Длина последовательности — это суммарное количество клеток, на которые переместилась шашка. Например, если шашку переместили на 4 клетки по диагонали, а потом на 2 по горизонтали, то длина будет равна 6.
В восьми строках дано описание поля. Каждая из этих строк состоит из восьми символов. Каждый из этих символов — это «.», если клетка пустая, «b», если в клетке стоит чёрная шашка, «w», если в клетке стоит белая шашка, или «W», если в клетке стоит белая дамка. Гарантируется, что количество чёрных шашек $$$n$$$ на доске удовлетворяет неравенству $$$1 \leq n \leq 15$$$.
Гарантируется, что у белых ровно одна шашка. Эта шашка изначально может быть дамкой. Белая шашка обязана быть дамкой, если изначально находится на границе поля.
В первой строке выведите «YES», если Ливси сможет победить, и «NO» в противном случае.
Если ответ «YES», то во второй строке выведите длину пути, который прошла белая шашка, и в третьей строке выведите $$$n + 1$$$ позицию, в которых побывала белая шашка в порядке посещения. Изначальная позиция тоже должна быть выведена.
Позиция — это строка из двух символов. Первый из них — это буква от «a» до «h», а второй — это цифра от «1» до «8». Первый символ — это координата по горизонтали (слева направо), а второй — координата по вертикали (снизу вверх).
........ ........ ........ ..b.b... ...w.... ........ ........ ........
NO
........ ..b..... .....b.. ..b.b... ...w.... ........ ........ ........
YES 13 d4 b6 d8 g5 a5
........ ...b.b.. ........ ........ ......b. .....w.. ........ ........
YES 9 f3 h5 e8 a4
...b.... ....b.b. ..b....b ....b... bWb...b. ...b.... ...b.b.. ........
YES 70 b4 f8 b8 g3 a3 a8 h1 h7 a7 g1 g8 a2 h2
