Шлях коня

Задано шахову дошку, яка складається з n×n клітинок, декілька з яких вирізано. Провести ходом коня через невирізані клітинки шлях мінімальної довжини з однієї клітинки в іншу.

Вхідні дані

У першому рядку задано число n (2 ≤ n ≤ 50). У наступних n рядках міститься по n символів. Символом # позначено вирізану клітинку, точкою - невирізану клітинку, @ - задані клітинки (таких символів два).

Вихідні дані

Якщо шлях побудувати неможливо вивести "Impossible", у противному випадку вивести таку ж карту, як і на вході, але помітити всі проміжні положення коня символом @.

Приклади