eolymp
bolt
Try our new interface for solving problems
Problems

The way a Knight

The way a Knight

Time limit 1 second
Memory limit 122 MiB

On a chessboard consisting of n × n cells, several of them are cut. Find the path of minimum length for a Knight from one cell to another. The Knight can’t go through cut cells.

Input data

The first row is set to the number n (2n50). Each of the next n lines contains n symbols. The symbol **\#**denotes the cut cell, the point is not a cut cell, and the symbol @ denotes the initial and final cell of the Knight's path (the chessboard contains two such characters).

Output data

If the path can not be constructed, print "Impossible". Otherwise, print the same map as the input, but check all Knight intermediate positions with the symbol @.

Examples

Input example #1
5
.....
.@@..
.....
.....
.....
Output example #1
.....
.@@..
...@.
.@...
.....
Input example #2
5
@..@.
..##.
.....
.....
.....
Output example #2
@..@.
..##.
.@@..
...@.
.@...
Input example #3
5
@....
..#..
.#...
.....
....@
Output example #3
Impossible