민철이는 어떤 미로에 갇히고 말았다.

미로를 탈출하기 위해 민철이는 다음 2가지 규칙대로 움직이기로 했다.

1. 오른쪽으로 이동한다.

2. 오른쪽으로 갈 수 없으면 아래로 이동한다.

미로에 갇힌 민철이는 출구를 찾거나 더 이상 움직일 수 없을 때까지 위 2가지 규칙대로만 움직인다.

미로의 구조가 0(이동 가능한 구역), 1(벽), 2(출구)로 주어졌을 때, 민철이의 이동 경로를 출력하는 프로그램을 작성하시오.

단, 민철이가 출발하는 지점은 9로 주어지며, 이동 경로도 9로 표기한다.

첫 번째 줄에 미로의 가로 크기 N(3 ≤ N ≤ 100)와 세로 크기 M(3 ≤ M ≤ 100)이 주어진다.

두 번째 줄부터 m + 1 번째 줄에 걸쳐 미로의 초기 상태Aij를 입력한다.

Aij가 9이면 민철이가 처음 출발하는 장소이며, Aij가 0이면 이동 가능한 곳이고, Aij가 1이면 벽으로 막혀있는 곳이다.

Aij가 2인 곳이 목적지이다.

미로는 항상 사방이 벽으로 막혀 있으며, 처음 입력할 때 9와 2는 단 한 곳만 가능하다.

민철이가 이동한 경로를 9로 표시해 출력한다.

목적지에 도달했으면 목적지인 2를 9로 바꿔서 출력하고, 도달하지 못했다면 마지막으로 이동 가능한 지역까지의 경로를 9로 표시한다.

TH1 TH1_B_W8