로봇과 하는 아이들 놀이

이 문제는 대화형 문제이다.

어린 미샤는 로봇과 아이들 놀이를 한다. 로봇은 $3 \times 3$ 칸으로 나뉘고 테두리로 둘러싸인 필드 위에 서 있다. 게임은 가운데 칸에서 시작하며 열 번의 행동으로 이루어진다. 각 행동은 구호를 외치거나 이웃한 칸으로 이동을 시도하는 것 중 하나이다. 구호는 기다리거나 단순히 재미로 쓴다.

특수한 칸이 하나 있지만 미샤는 그것이 어느 칸인지 미리 알지 못한다. 로봇은 특수한 칸으로 이동하면 이를 알린다. 목표는 정확히 열 번째 행동에서 특수한 칸으로 이동하는 것이다.

미샤는 텍스트 입출력으로 로봇과 통신한다. 인식하는 명령은 다음과 같다.

• echo 구호: 구호를 외친다.
• move north: 북쪽으로 한 칸 이동한다.
• move east: 동쪽으로 한 칸 이동한다.
• move south: 남쪽으로 한 칸 이동한다.
• move west: 서쪽으로 한 칸 이동한다.

구호 명령마다 로봇은 구호를 크게 읽고 텍스트로 다시 출력한다. 구호를 외치는 동안 로봇은 움직이지 않는다. 로봇은 ASCII 코드 32부터 126까지의 문자로 이루어진, 최대 256자 길이의 구호를 정확히 처리한다.

이동 명령마다 로봇은 다음 네 단어 중 하나를 출력한다.

• bump: 벽에 부딪혀 이동하지 못하고 같은 칸에 머문다.
• moved: 일반 칸으로 이동했다.
• found: 처음 아홉 번의 행동 중 하나에서 특수한 칸으로 이동했다.
• win: 열 번째 행동에서 특수한 칸으로 이동했다.

열 번째 행동에서 로봇이 win을 출력하도록 미샤가 게임을 진행하는 것을 도와라.

특수한 칸은 미리 정해져 있으며, 대회가 진행되는 동안 바뀌지 않는다.