Problems

# The way a Knight

# The way a Knight

Given 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

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

#### Output

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

Input example #1

5 ..... .@@.. ..... ..... .....

Output example #1

..... .@@.. ...@. .@... .....

Input example #2

5 @..@. ..##. ..... ..... .....

Output example #2

@..@. ..##. .@@.. ...@. .@...

Input example #3

5 @.... ..#.. .#... ..... ....@

Output example #3

Impossible