Путь коня#1064

Путь коня

1 секунда
122,174 мегабайта
Very easy

Дана шахматная доска размером n \times n, на которой некоторые клетки удалены. Найдите кратчайший путь, по которому конь может пройти от одной клетки до другой, используя только не удалённые клетки.

Input

Первая строка содержит целое число (2 \leq n \leq 50). Каждая из следующих строк содержит по символов. Символ обозначает удалённую клетку, символ точка — не удалённую клетку, а символ отмечает начальную и конечную клетки пути коня (на доске ровно две такие клетки).

Output

Если построить такой путь невозможно, выведите Impossible. В противном случае выведите ту же карту, что и во входных данных, но отметьте все клетки, через которые проходит конь в промежуточных позициях, символом .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading