В таблице из n строк и n столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.

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

В первой строке находится число n (2 ≤ n ≤ 40), в каждой из следующих n строк - по n символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика.

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

В первой строке вывести Y, если движение возможно, или N, если нет. Если движение возможно, то далее следуют n строк по n символов - как и на вводе, но X, а также все точки на пути заменяются плюсами.