로봇

$n \times m$ 격자로 표현되는 필드 위에 로봇이 있다. 격자의 일부 칸은 벽이다.

로봇은 up, down, left, right 네 가지 명령을 받는다.

로봇이 현재 좌표 $(x, y)$에 있다고 하자. 각 명령을 실행했을 때의 결과는 다음과 같다.

• up : $x = 0$이거나 $(x - 1, y)$가 벽이면 로봇은 움직이지 않는다. 그렇지 않으면 로봇은 $(x - 1, y)$로 이동한다.
• down : $x = n - 1$이거나 $(x + 1, y)$가 벽이면 로봇은 움직이지 않는다. 그렇지 않으면 로봇은 $(x + 1, y)$로 이동한다.
• left : $y = 0$이거나 $(x, y - 1)$이 벽이면 로봇은 움직이지 않는다. 그렇지 않으면 로봇은 $(x, y - 1)$로 이동한다.
• right: $y = m - 1$이거나 $(x, y + 1)$이 벽이면 로봇은 움직이지 않는다. 그렇지 않으면 로봇은 $(x, y + 1)$로 이동한다.

로봇의 시작 위치는 $(a, b)$ 또는 $(c, d)$ 중 하나이다. 로봇이 $(a, b)$에서 출발하든 $(c, d)$에서 출발하든 항상 $(0, 0)$에서 끝나도록 하는, 길이가 $q$ 이하인 명령열을 찾아라. 문제의 제약을 만족하는 모든 입력에 대해 답이 존재함을 증명할 수 있다.

• $1 \le n \le 10$
• $1 \le m \le 10$
• $0 \le a \le n - 1$
• $0 \le b \le m - 1$
• $0 \le c \le n - 1$
• $0 \le d \le m - 1$
• $g[0][0] = g[a][b] = g[c][d] = 0$
• 로봇을 $(a, b)$에서 $(0, 0)$으로 이동시키는 유한한 명령열이 존재한다
• 로봇을 $(c, d)$에서 $(0, 0)$으로 이동시키는 유한한 명령열이 존재한다
• $q = 700$