상규는 요즘 유행하는 유명게임 “카트라이더”의 랭커이다.

하지만 전 세계적으로 카트라이더 붐이 온 지금, 다른 유저들에게 따라잡힐지도 모른다는 불안감에 최적의 경로를 연구하고 있다.

카트라이더는 코너를 돌 때, 코너의 맞은편 벽면에 붙어서

코너의 가장 안쪽 라인을 밟은 뒤에 다음 길의 중간 라인을 밟는 것이

가장 최적의 코스로 알려져있다.

(통칭 OUT-IN-OUT)

하지만 벽면에 붙지 못하는 경우에는 코너의 가장 안쪽 라인을 밟는것을 최우선으로 여긴다.

또한 상규가 플레이하는 모든 트랙은 벽에 가까워질수록 가속이 잘 받는 특징이 있으며 시작부분의 바로 옆에 코너가 있을 수 없다 (벽은 있을 수 있다). 카트는 다음과 같은주행을 할 수 있다.

1. 앞으로 이동

2. 대각선으로 이동

3. 회전

앞으로 이동할때 속도는 1m/s, 대각선으로 이동할때 속도는 0.5m/s, 벽면에 붙어 앞으로 이동할때의 속도는 2m/s이다.

이 때, 유저가 이동할 수 있는 가장 최적의 경로와 기록을 구해라.

벽은 한 블럭당 1m이다.

길의 너비는 모두 3 이상의 홀수로 되어있다.

길의 시작은 모두 앞으로(위쪽으로) 가는 경로이다.

다음 코너가 없을 시 전 코너의 반대편으로 가는 것이 최적의 경로이다.

하단에 입력 설명과 출력 설명을 참고해라

입력 예시

7 8
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 4 0 1 0 2 0

출력예시

0 0 0 0 0 0 0 
0 0 0 0 0 0 0 
0 0 0 3 0 0 0 
0 0 3 1 3 0 0 
0 3 0 1 0 3 0 
3 0 0 1 0 0 3 
3 0 0 1 0 0 3 
0 3 0 1 0 3 0 
8.0

첫 줄에 가로와 세로의 넓이를 입력받는다.

r 가로

c 세로

두번째 줄부터 트랙을 표시한다.

시작지점(4), 길(0), 벽(1), 도착지점(2)

출력 설명

트랙에 최적의 이동 경로(3)를 표시하여 트랙을 나타낸다.

마지막줄에 기록을 표시한다.