문제를 푸는 문제 (주령구)

이 문제는 제출할 수 없습니다. "문제를 푸는 문제" 문제를 참조하세요.

경주 안압지에서 출토된 신라 시대의 주령구는 육팔면체와 비슷한 모양으로, 주령을 어겼을 때 벌을 가감하는 데 쓰이던 주사위의 일종입니다. 삼각형처럼 보이는 육각형 면 8개와 사각형 면 6개로 이루어져 있습니다.

그림 1: 온양에서 발견된 주령구.

이 주령구를 굴리며 놀아 봅시다. 처음에는 바닥에 맞닿은 면과, 그 면과 변을 공유하는 인접한 면이 주어집니다. 인접한 면은 바닥에 맞닿은 변의 아래 방향에 있으며, 주령구의 방향을 나타내기 위해 주어집니다. 이어서 입력으로 주어지는 커맨드를 한 글자씩 순서대로 처리합니다. 커맨드는 L, R, U, D이며, 각각 왼쪽, 오른쪽, 위쪽, 아래쪽 방향에 대응합니다. 커맨드가 주어지면 현재 면에서 그 방향에 인접한 면을 찾고, 그 면이 바닥에 닿을 때까지 주령구를 굴립니다. 회전이 끝나면 이전에 바닥에 맞닿아 있던 면이 아래를 향하도록 주령구의 방향을 맞춥니다.

육각형 면의 짧은 변은 고려하지 않습니다. 이 방향으로는 회전하지 않으며, 이 방향으로 인접한 면도 없다고 봅니다. (육각형 면은 삼각형처럼 생각하면 됩니다.) 따라서 시행할 수 없는 회전, 즉 육각형 면이 바닥에 맞닿아 있는데 위쪽 회전을 해야 하는 경우에는 그 회전을 무시합니다.

주어진 커맨드를 순서대로 모두 시행한 뒤, 마지막에 바닥에 맞닿아 있는 면을 출력하세요.

실제 주령구는 모든 면이 한자로 적혀 있으므로, 편의상 아래 전개도를 화면에서 튀어나오는 방향이 안쪽을 향하도록 접은 육팔면체를 대신 사용합니다.

\

그림 2: 사용할 육팔면체. 올해 구데기컵 문제를 떠올리게 하는 단어를 넣었으니, 심심하면 뽑아서 접어 보는 것도 재미있을 것입니다.

첫째 줄에 처음에 바닥에 맞닿아 있는 면과, 그 인접한 면 중 아래를 향하게 할 면이 공백을 사이에 두고 주어집니다.

둘째 줄에 L, R, U, D와 (...)n으로 이루어진 문자열이 주어집니다. 문자열의 길이는 1 이상이고 200,000을 넘지 않습니다. L, R, U, D는 각각 왼쪽, 오른쪽, 위쪽, 아래쪽으로 주령구를 굴리라는 커맨드입니다. (...)n은 괄호 안의 문자열을 n번 반복하라는 뜻입니다. 이때 n은 1 이상 $10^9$ 미만의 정수입니다.

예를 들어 L(U(LR)3D)2R은 LULRLRLRDULRLRLRDR과 같습니다.

주어진 커맨드대로 주령구를 굴린 뒤, 마지막에 바닥에 맞닿아 있는 면을 출력합니다.