개미

면접 대비

시간 제한1초메모리 제한128 MB

요약

서로 반대 방향으로 이동하다 만난 두 개미 그룹이 매초 인접한 반대 방향 개미와 자리를 바꿀 때 T초 후의 배열을 구하는 문제입니다.

문제

두 개미 무리가 좁은 길에서 서로 마주 보고 이동한다.

첫 번째 무리의 개미들은 왼쪽에서 오른쪽으로, 두 번째 무리의 개미들은 오른쪽에서 왼쪽으로 이동한다. 두 무리가 처음 만나는 순간 길 위의 순서는 첫 번째 무리를 뒤집은 뒤 두 번째 무리를 이어 붙인 순서가 된다.

이후 1초가 지날 때마다, 바로 앞에 반대 방향으로 이동하는 개미가 있는 개미는 그 개미를 뛰어넘어 위치를 바꾼다. 한 초 동안 일어나는 모든 점프는 동시에 처리된다.

예를 들어 첫 번째 무리가 ABC, 두 번째 무리가 DEF라면 처음 순서는 CBADEF이다. 1초 뒤에는 A와 D가 서로 위치를 바꾸어 CBDAEF가 되고, 2초 뒤에는 CDBEAF가 된다.

T초가 지난 뒤 길 위의 개미 순서를 구하라.

첫째 줄에 첫 번째 무리의 개미 수 N1과 두 번째 무리의 개미 수 N2가 주어진다.

다음 두 줄에는 첫 번째 무리와 두 번째 무리의 개미 순서가 각각 주어진다. 각 개미는 알파벳 대문자 하나로 표현되며, 두 무리 전체에서 같은 알파벳은 두 번 나오지 않는다.

마지막 줄에 정수 T가 주어진다. (0 <= T <= 50)

T초가 지난 뒤 길 위의 개미 순서를 출력한다.