자동 편집

awk나 sed 같은 텍스트 처리 도구를 사용하면 스크립트에 따라 일련의 편집 작업을 자동으로 수행할 수 있습니다. 이 문제에서는 고정된 규칙 집합에 따라 한 줄의 텍스트 안에서 여러 번의 문자열 치환을 수행하는 경우를 다룹니다. 각 규칙은 아래와 같이 찾을 문자열과, 그것을 바꿀 문자열을 지정합니다.

주어진 텍스트를 편집하는 방법은 다음과 같습니다. 첫 번째 규칙부터 시작합니다. 텍스트에서 찾을 문자열이 처음 나타나는 부분을 바꿀 문자열로 치환한 뒤, 바뀐 텍스트에 대해 같은 치환을 다시 시도합니다. 찾을 문자열이 더 이상 텍스트에 나타나지 않을 때까지 반복한 다음, 그 다음 규칙으로 넘어갑니다. 모든 규칙을 처리할 때까지 계속합니다. 다음 사항에 유의하세요. (1) 찾을 문자열을 탐색할 때는 항상 텍스트의 맨 앞에서부터 탐색을 시작합니다. (2) 어떤 규칙의 사용을 마치면(찾을 문자열이 더 이상 나타나지 않아서) 그 규칙은 두 번 다시 사용하지 않습니다. (3) 대소문자를 구분합니다.

예를 들어 다음 줄에서 시작한다고 합시다.

banana boat

위 규칙들을 적용하면 변환 과정은 아래와 같습니다. 찾을 문자열이 나타난 부분은 기울임체로, 치환된 부분은 굵게 표시했습니다. 규칙 1은 두 번, 규칙 2는 한 번, 규칙 3은 0번, 규칙 4는 한 번 사용되었습니다.

입력은 하나 이상의 테스트 케이스로 이루어지며, 그 뒤에 오직 0(영) 하나만 있는 줄이 와서 입력의 끝을 알립니다. 각 테스트 케이스는 규칙의 개수가 적힌 줄로 시작하며, 이 값은 1 이상 10 이하입니다. 각 규칙은 두 줄로 주어지는데, 첫 번째 줄은 찾을 문자열, 두 번째 줄은 바꿀 문자열입니다. 모든 규칙 다음에는 편집할 텍스트가 담긴 줄이 옵니다.

각 테스트 케이스마다 최종적으로 편집된 텍스트를 한 줄에 출력합니다.

찾을 문자열과 바꿀 문자열의 길이는 모두 최대 80자입니다. 찾을 문자열은 최소 한 글자 이상이지만, 바꿀 문자열은 비어 있을 수 있습니다(입력에서는 빈 줄로 표시됩니다). 편집 과정 중에 텍스트의 길이는 최대 255자까지 커질 수 있지만, 최종 출력 텍스트의 길이는 80자 미만입니다.

첫 번째 예제 테스트 케이스는 위에서 보인 예시에 해당합니다.