# The way a Knight

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 122.174 megabytes

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

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 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

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 #1

Answer #1

Input #2

Answer #2

Input #3

Answer #3

Submissions 2K

Acceptance rate 44%