31857번 - 사탕 공장

안즈는 사탕을 정말 좋아한다. 그래서 안즈는 그동안 벌었던 모든 돈을 투자해 사탕 공장을 세웠다.

사탕 공장의 마지막 공정인 포장 단계에서는 다양한 종류의 사탕을 두 개의 컨베이어 벨트와 하나의 집게를 이용해 조작한다. 컨베이어 벨트는 \(N\)개의 칸으로 이루어져 있으며, 집게는 컨베이어 벨트의 첫 번째 칸부터 임의의 칸까지 모든 사탕을 한 번에 집을 때 쓰인다.

구체적으로 가능한 조작의 종류는 다음과 같다. 초기에 각 컨베이어 벨트의 모든 칸에는 하나의 사탕이 올려져 있다.

• \(S\): 집게를 이용해 두 컨베이어 벨트의 첫 번째 칸부터 \(R\) 번째 칸 사이에 위치한 모든 사탕을 각각 서로 교환한다. \(R\)은 현재 집게의 크기이다.
  • 다시 말하면, 1번 컨베이어 벨트의 첫 번째 칸에 있는 사탕과 2번 컨베이어 벨트의 첫 번째 칸에 있는 사탕을 서로 교환하고, 두 번째 칸에 있는 사탕을 서로 교환하고, ..., 마지막으로 \(R\) 번째 칸에 있는 사탕을 서로 교환한다.
• \(L\) \(x\): \(x\)번 컨베이어 벨트를 한 칸 왼쪽으로 움직인다.
  • 즉, 첫 번째 칸에 있는 사탕을 제외한 모든 사탕의 위치가 \(p\) 번째 칸에서 \((p−1)\) 번째 칸으로 바뀐다. 첫 번째 칸에 있는 사탕은 \(N\) 번째 칸으로 이동한다.
• \(R\) \(x\): \(x\)번 컨베이어 벨트를 한 칸 오른쪽으로 움직인다.
  • 즉, \(N\) 번째 칸에 있는 사탕을 제외한 모든 사탕의 위치가 \(p\) 번째 칸에서 \((p+1)\) 번째 칸으로 바뀐다. \(N\) 번째 칸에 있는 사탕은 첫 번째 칸으로 이동한다.
• \(I\): 집게의 크기를 \(1\) 늘린다. 집게의 크기가 \(N\)보다 커지는 입력은 들어오지 않는다.
• \(D\): 집게의 크기를 \(1\) 줄인다. 집게의 크기가 \(1\)보다 작아지는 입력은 들어오지 않는다.

안즈는 모든 조작이 끝난 후에 사탕이 어떻게 배열되어 있을지 알고 싶어졌다. 하지만 안즈는 이를 직접 하기에는 너무 귀찮았기 때문에, 여러분에게 해결을 부탁했다.

첫 번째 줄에 두 컨베이어 벨트의 크기 \(N\), 초기 집게의 크기 \(R\), 조작의 횟수 \(Q\)가 주어진다.

두 번째 줄에 1번 컨베이어 벨트의 맨 왼쪽 칸부터 맨 오른쪽 칸까지 올려져 있는 사탕이 차례대로 공백 없이 주어진다.

세 번째 줄에 2번 컨베이어 벨트의 맨 왼쪽 칸부터 맨 오른쪽 칸까지 올려져 있는 사탕이 차례대로 공백 없이 주어진다.

각 사탕은 알파벳 대문자를 사용하여 나타낸다.

이후 \(Q\)줄에 걸쳐 처리해야 하는 조작이 하나씩 주어진다.

모든 조작을 순서대로 처리한 후,

첫 번째 줄에 1번 컨베이어 벨트에 올려져 있는 사탕을 입력과 같은 형식으로 출력한다.

두 번째 줄에 2번 컨베이어 벨트에 올려져 있는 사탕을 입력과 같은 형식으로 출력한다.

• \(1 \le N \le 500{,}000\)
• \(1 \le R \le N\)
• \(1 \le Q \le 500{,}000\)
• \(1 \le x \le 2\)