트리뷰트 (에디터)

문제

이 문제는 세상에서 가장 뛰어난 편집기에 관한 이야기가 아니라, 그저 그 편집기에 바치는 헌사(tribute)일 뿐입니다.

Tenacious eDitor(줄여서 td)는 어느 모달 편집기의 강력함을 흉내 내려는 시도입니다. 하지만 버그가 많기로 악명이 높아, 여러분은 그 버그 몇 가지를 고치는 일을 맡게 되었습니다.

현재 배포된 td의 가장 큰 문제는 화면에 찍혀야 할 텍스트와 명령을 구분하지 못한다는 점입니다. 사용자가 x를 입력하려고 하면, 편집기는 이를 바로 앞 글자를 지우라는 명령으로 해석해 버립니다. 다행히 명령은 대소문자를 구분하고 각 명령은 한 글자짜리이므로, 마치 해커 흉내를 내는 십대가 친 것처럼 보이기만 한다면 어떤 텍스트든 결국 만들어 낼 수 있습니다.

편집은 처음에 비어 있는 편집 버퍼에서 이루어집니다. 커서는 각 출력 글자 사이의 위치인 '간격(gap)'에 놓입니다. 명령이 아닌 문자가 입력되면 그 문자는 커서 바로 오른쪽에 삽입되고, 커서는 새 문자의 오른쪽 간격으로 이동합니다. 글자가 하나도 없는 줄에는 간격이 하나, 출력 글자가 하나인 줄에는 간격이 둘(앞과 뒤), 둘이면 셋, 이런 식으로 늘어납니다.

현재 구현된 명령은 다음과 같습니다.

명령 키	동작	동작 후 커서 위치
`x`	커서 바로 왼쪽 글자를 삭제한다.	한 간격 왼쪽
`K`	커서 왼쪽의 공백이 아닌 글자를 첫 공백이나 줄 시작을 만날 때까지 모두 삭제한다. 왼쪽 글자가 공백이면 아무것도 삭제하지 않는다.	멈춘 글자의 오른쪽 간격
`c`	커서 왼쪽 글자를 복제하여 커서 오른쪽에 삽입한다.	복제된 글자의 오른쪽 간격
`D`	커서 왼쪽의 공백이 아닌 글자를 첫 공백이나 줄 시작을 만날 때까지 모두 복제하여 커서 오른쪽에 삽입한다. 왼쪽 글자가 공백이면 아무것도 복제하지 않는다.	복제된 글자 중 가장 오른쪽 글자의 오른쪽 간격
`R`	커서 왼쪽의 공백이 아닌 글자를 첫 공백이나 줄 시작을 만날 때까지 모두 뒤집는다. 왼쪽 글자가 공백이면 아무것도 뒤집지 않는다.	변화 없음
`p`	커서 왼쪽의 모든 글자를 삭제한다.	가장 왼쪽 간격
`W`	커서 오른쪽의 모든 글자를 삭제한다.	변화 없음
`h`	커서를 한 간격 왼쪽으로 옮긴다.	한 간격 왼쪽
`L`	커서를 한 간격 오른쪽으로 옮긴다.	한 간격 오른쪽
`f`	커서를 줄의 첫 간격으로 옮긴다.	가장 왼쪽 간격
`G`	커서를 줄의 마지막 간격으로 옮긴다.	가장 오른쪽 간격
그 밖의 문자	그 문자를 커서 오른쪽의 편집 버퍼에 삽입한다.	한 간격 오른쪽

이 문제에서 등장할 수 있는 문자는 대문자, 소문자, 숫자, 공백뿐입니다.

줄 중간에 문자가 삽입되면 그 뒤의 모든 문자가 오른쪽으로 한 칸씩 밀립니다(삽입 모드). 줄 끝이 아닌 곳에서 문자가 삭제되면 그 뒤의 모든 문자가 왼쪽으로 한 칸씩 당겨집니다.

의미 있는 동작을 할 수 없는 명령(첫 간격보다 왼쪽이나 마지막 간격보다 오른쪽으로 이동하려는 경우, 지울 것이 없는데 지우려는 경우 등)은 아무 일도 하지 않으며, 출력 문자로도 나타나지 않습니다.

각 입력 줄은 서로 독립적인 td 세션이며, 모든 세션은 빈 편집 버퍼에서 시작합니다.

사용자가 입력한 키 입력이 주어질 때, 실제로 버퍼에 남는 텍스트를 구하세요.

입력

첫째 줄에 데이터 집합의 개수를 나타내는 정수 $N$ ($1 \le N \le 100$)이 주어진다.

각 데이터 집합은 위에서 설명한 문자들로 이루어진 한 줄로, 앞뒤에 공백이 없다. 각 줄의 길이는 $1$자 이상 $100$자 이하이며, 한 번의 td 세션 동안 사용자가 입력한 키 입력을 나타낸다.

출력

각 데이터 집합에 대해, 편집 버퍼의 최종 내용을 출력하되 커서 위치에 캐럿(^)을 표시한다.