Superknight

A superknight stands on a square of a chessboard and wants to reach another square in the fewest possible moves. Some squares are blocked. The knight may jump over them but may not land on them.

A regular knight moves two rows and one column, or two columns and one row, in each move (left figure). It can jump over blocked squares, but it cannot land on them (middle figure).

A superknight differs from a regular knight in one way. It may make one supermove on its path, and at most one. A supermove moves it three rows and one column, or three columns and one row (right figure). Write a program that finds a path from a given start square to a given destination square using the fewest possible moves.

The first line contains $R$, the number of rows, and $V$, the number of columns of the board ($3 \le R \le 100$, $3 \le V \le 100$). Each of the following $R$ lines contains exactly $V$ characters. '@' marks the knight's starting square, '*' marks the destination, '.' marks a free square, and '#' marks a blocked square.

The first line of output contains $K$, the minimal number of moves needed to reach the destination. Each of the following $K + 1$ lines contains two integers $r_i$ and $v_i$, the row and column of the squares the knight visits, in the order visited. Rows are numbered $1 \ldots R$ from top to bottom, and columns are numbered $1 \ldots V$ from left to right. You may assume the destination is reachable in every test case. If several paths use the minimal number of moves, output any one of them.