18834번 - 문제를 푸는 문제 (주령구) 서브태스크채점 준비 중

이 문제에는 제출할 수 없다. "문제를 푸는 문제" 문제를 참조하라.

경주 안압지에서 출토된 신라 시대의 주령구는 육팔면체와 유사한 형태로, 주령을 위반할 때 그 벌을 가감하는 용도로 사용되던 주사위의 일종입니다. 삼각형처럼 보이는 육각형 면 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⁹ 미만의 정수입니다.

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

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

문자열은 다음의 문자로만 구성됩니다: D.

문자열은 다음의 문자들로만 구성됩니다: LRUD.

n ≤ 3.

추가 제약 조건이 없습니다.