Kolone

개미들은 이동할 때 첫 번째 개미를 제외한 모든 개미가 다른 개미 뒤에 서도록 줄을 짓는다. 반대 방향으로 이동하는 두 개미 줄이 두 줄이 함께 지나가기에는 너무 좁은 통로에서 마주치면 어떤 일이 벌어지는지는 잘 알려져 있지 않다. 한 이론에 따르면, 그 상황에서 개미들은 서로를 뛰어넘는다고 한다.

두 줄이 만난 순간부터 매초 각 개미는 자기 앞의 개미를 뛰어넘어(또는 서로 합의한 대로 뛰어넘어져서) 두 개미가 자리를 바꾸는데, 이는 상대 개미가 반대 방향으로 이동하고 있을 때만 일어난다. \(T\)초 후 개미들의 순서를 구하시오.

첫째 줄에 두 정수 \(N_1\)과 \(N_2\)가 주어진다. 각각 첫 번째 줄과 두 번째 줄에 있는 개미의 수이다.

다음 두 줄에는 첫 번째 줄과 두 번째 줄의 개미 순서(맨 앞부터 맨 뒤까지)가 주어진다. 각 개미는 영어 알파벳 대문자로 유일하게 결정된다(이 글자는 두 줄을 통틀어 유일하다).

입력의 마지막 줄에 정수 \(T\) (\(0 \le T \le 50\))가 주어진다.

\(T\)초 후 개미들의 순서를 한 줄에 출력한다. 우리의 시점에서 첫 번째 개미 줄은 왼쪽에서, 두 번째 줄은 오른쪽에서 온다.

riseoj 작성

출처 COCI 2006/2007 Contest 2