Дана шахматная доска, состоящая из n × n клеток, несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной клетки в другую.

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

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

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

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