25319번 - Twitch Plays VIIIbit Explorer 스페셜 저지

생방송 플랫폼 Twitch에서 “Twitch Plays Pokémon”이라는 컨텐츠가 큰 유행을 끈 적이 있다. 이 방송은 시청자가 채팅으로 명령을 입력하면 그 명령이 게임에 반영되는 독특한 시스템을 사용해, 수십만 명이 합심해 하나의 게임을 진행한다는 특별한 경험을 제공했다. 막 데뷔한 스트리머 에리는 이 시스템을 빌려 “Twitch Plays VIIIbit Explorer” 컨텐츠를 진행하기로 했다.

VIIIbit Explorer는 캐릭터를 조종해 던전을 탈출하는 간단한 게임이다. 던전은 격자로 나뉘어진 직사각형 모양이며, 몇몇 격자칸에는 아이템이 놓여 있다. 시청자는 다음과 같은 명령들을 입력해 캐릭터를 조종할 수 있다.

• U, D, L, R: 캐릭터를 위, 아래, 왼쪽, 오른쪽으로 한 칸 움직인다. 단, 던전 바깥으로 이동하게 되는 경우 던전을 둘러싸고 있는 용암에 빠져 게임 오버된다.
• P: 캐릭터가 위치한 칸에 놓여 있는 아이템을 줍는다. 단, 아이템이 없는 칸에서 이 명령을 사용하는 경우 바닥이 무너져 게임 오버된다.

평화롭게 컨텐츠를 진행하던 중, EJN의 Twitch 스트리머 후원 서비스인 Twip으로 미션 하나가 들어왔다.

이 미션을 수락하면 캐릭터는 새로운 던전으로 이동하게 됩니다. 던전은 $N$행 $M$열 크기이며 캐릭터는 가장 왼쪽 위의 칸에서 출발합니다.

이 던전의 모든 칸에는 아이템이 하나씩 놓여 있고, 각 아이템에는 알파벳이 하나씩 적혀 있습니다. 던전을 탐험하며 주운 아이템들을 주운 순서대로 나열했을 때, 그 문자열이 정확히 제 아이디와 일치하면 가진 아이템들이 모두 없어지고 캐릭터가 한 단계 강화됩니다.

던전을 탈출하기 위해서는 숨겨진 포탈을 작동시켜야 합니다. 캐릭터를 던전의 가장 오른쪽 아래 칸에 위치시킨 뒤, “ALL PERFECT”를 외치면 숨겨진 포탈이 작동할 것입니다. 단, 캐릭터가 아이템을 하나라도 가지고 있다면 포탈은 작동하지 않습니다.

캐릭터를 한 번 강화시킬 때마다 미션 상금으로 $1$억 원씩이 추가됩니다. 행운을 빕니다!

“$1$억 원?!” 상금에 큰 감명을 받은 에리는 당장 미션을 수락했다. 그리고 방해되는 시청자들을 제거하기 위해 자신만 채팅을 칠 수 있도록 채팅방을 얼려 버렸다.

이제 남은 것은 최대한 많은 상금을 얻으면서 던전을 탈출할 수 있는 이동 방법을 찾고, 한 글자씩 채팅으로 입력하는 것뿐이다. 에리를 도와 주면 상금을 조금 나눠 줄지도 모르니, 그러한 이동 방법을 찾아 주자.

첫 번째 줄에는 던전의 세로 길이 $N$, 가로 길이 $M$, 그리고 아이디의 길이 $\lvert S\rvert$가 공백으로 구분되어 주어진다. $(2\le N,M\le 50$; $1\le\lvert S\rvert\le 1\, 000)$

두 번째 줄부터 다음 $N$개의 각 줄에는 영어 소문자로 이루어진 길이 $M$의 문자열이 주어진다. $i$번째 문자열의 $j$번째 글자는 위에서 $i$번째, 왼쪽에서 $j$번째 칸에 있는 아이템에 적힌 알파벳을 의미한다.

마지막 $N+2$번째 줄에는 영어 소문자로 이루어진 아이디 $S$가 주어진다.

첫 번째 줄에 $C$와 $L$을 공백으로 구분하여 출력한다. 이는 캐릭터를 총 $C$번 강화할 수 있고, 탈출을 위해 포탈을 작동시키기 전까지 $L$번의 행동이 필요함을 의미한다. 이때, $C$는 가능한 방법 중 가장 큰 값이어야 한다.

두 번째 줄에는 길이 $L$의 문자열을 출력한다. 이 문자열의 $i$번째 문자는 $i$번째로 진행된 행동이어야 하며, 실제로 출력에 따라 행동을 수행했을 때 캐릭터가 $C$번 강화되었고 “ALL PERFECT”를 외치는 즉시 던전을 탈출할 수 있는 상태여야 한다.

$L$은 $1$ 이상 $1\, 000\, 000$ 이하여야 하지만, 이동 횟수가 최소일 필요는 없다.

가능한 모든 입력에 대해서 위 출력 조건을 만족하는 출력이 항상 존재함을 증명할 수 있다.

가능한 답이 여러 가지라면 그중 아무거나 출력한다.