저녁 메뉴는 개구리

"자크 삼촌, 저녁은 뭐예요?"

"10분 뒤에 다시 물어보렴." 자크 삼촌은 다 쓰러져 가는 오두막 앞, 고속도로 갓길에 앉은 지친 개구리를 바라보며 이렇게 답한다.

개구리가 차량으로 붐비는 도로를 건너기 시작한다. 개구리 뒷다리를 삶을 물부터 올릴지, 어젯밤에 남은 주머니쥐를 데울지 정해야 한다. Swamp 'Puter XL2를 켜고 개구리가 건너편 갓길에 닿을지 아니면 로드킬로 끝날지 판정하는 프로그램을 짠다.

오두막 앞 도로는 10 x 10 격자다. 0번 행과 9번 행은 갓길, 1번 행부터 8번 행까지는 차로이며 열 번호는 0번부터 9번까지다.

 행    0 1 2 3 4 5 6 7 8 9   <- 열
  0    . . . . . . . . . .   출발 갓길
  1    . . . . . . . . . .   차로, 차량은 왼쪽으로
  2    . . . . . . . . . .   차로, 차량은 왼쪽으로
  3    . . . . . . . . . .   차로, 차량은 왼쪽으로
  4    . . . . . . . . . .   차로, 차량은 왼쪽으로
  5    . . . . . . . . . .   차로, 차량은 오른쪽으로
  6    . . . . . . . . . .   차로, 차량은 오른쪽으로
  7    . . . . . . . . . .   차로, 차량은 오른쪽으로
  8    . . . . . . . . . .   차로, 차량은 오른쪽으로
  9    . . . . . . . . . .   도착 갓길

개구리와 차량은 턴 단위로 움직인다.

한 번의 시도를 시작하기 전에 개구리는 0번 행의 칸 하나를 고른다.
시도를 시작할 때 각 차량은 1번 행부터 8번 행 사이의 어느 열에 놓여 있다.
한 턴은 두 단계다. 먼저 개구리가 열을 그대로 둔 채 목적지인 9번 행 쪽으로 한 행 내려간다. 세상에서 제일 똑똑한 개구리는 아니다. 그다음 모든 차량이 동시에 n칸 움직인다. 1번 행부터 4번 행의 차량은 왼쪽으로, 5번 행부터 8번 행의 차량은 오른쪽으로 가며 n은 그 차량의 속도다. 격자 밖으로 나간 차량은 반대편에서 다시 들어온다. -1번 열로 갈 차량은 9번 열에, -2번 열로 갈 차량은 8번 열에, 10번 열로 갈 차량은 0번 열에, 11번 열로 갈 차량은 1번 열에 놓인다.
0번 행의 출발 열 가운데 하나라도 개구리를 살려서 9번 행까지 보내면 개구리는 고속도로를 건넌 것이다. 세상에서 제일 멍청한 개구리도 아니라서, 그런 열이 있으면 반드시 그 열을 고른다.
개구리가 차량과 같은 칸에 놓이는 순간 로드킬이 된다. 그런 일은 두 가지 경우에 일어난다. 개구리가 차량이 이미 있는 칸으로 내려가거나, 차량이 개구리가 있는 칸을 지나가거나 그 칸으로 들어와 개구리를 치는 경우다.

입력은 비어 있지 않으며 데이터 집합은 최대 100개다. 데이터 집합 사이에 빈 줄은 없다.

데이터 집합 하나는 시도 한 번의 초기 상태를 세 부분으로 나타낸다.

START 한 줄.
1번 행부터 8번 행까지를 차례로 나타내는 여덟 줄. 각 줄에는 열마다 하나씩 정수 10개가 공백 하나로 구분되어 있다. 0은 빈 칸을 뜻한다. $1 \le N \le 9$ 인 값 N은 그 칸에 속도 N인 차량이 있다는 뜻이다. 같은 행의 차량은 속도가 모두 같고 모든 차량이 동시에 움직이므로, 차량이 다른 차량을 지나치거나 다른 차량이 있는 칸에 들어가는 일은 없다.
END 한 줄.

저녁 메뉴는 개구리

문제

입력

출력