슈퍼나이트

슈퍼나이트는 체스판의 어떤 칸에 놓여 있으며, 가능한 한 적은 이동 횟수로 다른 칸에 도달하려고 한다. 일부 칸은 막혀 있다. 나이트는 그 칸을 뛰어넘을 수는 있지만, 그 칸에 도착할 수는 없다.

일반 나이트는 한 번의 이동에서 두 행과 한 열, 또는 두 열과 한 행만큼 움직인다(왼쪽 그림). 막힌 칸은 뛰어넘을 수 있지만 그 칸에 도착할 수는 없다(가운데 그림).

슈퍼나이트는 일반 나이트와 한 가지 점에서 다르다. 경로 중에 슈퍼무브를 최대 한 번 할 수 있다. 슈퍼무브는 세 행과 한 열, 또는 세 열과 한 행만큼 움직인다(오른쪽 그림). 주어진 출발 칸에서 목적 칸까지 최소 이동 횟수로 가는 경로를 찾는 프로그램을 작성하시오.

첫 줄에 보드의 행 수 $R$과 열 수 $V$가 주어진다($3 \le R \le 100$, $3 \le V \le 100$). 이어지는 $R$개의 줄에는 각각 정확히 $V$개의 문자가 주어진다. '@'는 나이트의 출발 칸, '*'는 목적 칸, '.'은 빈 칸, '#'은 막힌 칸을 뜻한다.

첫 줄에 최소 이동 횟수 $K$를 출력한다. 이어지는 $K + 1$개의 줄에는 나이트가 방문하는 칸의 행 번호 $r_i$와 열 번호 $v_i$를 방문 순서대로 출력한다. 행은 위에서 아래로 $1 \ldots R$, 열은 왼쪽에서 오른쪽으로 $1 \ldots V$ 번호를 매긴다. 모든 테스트 케이스에서 목적 칸에 도달할 수 있다고 가정해도 된다. 최소 이동 횟수의 경로가 여러 개라면 그중 아무거나 출력하면 된다.