GIF 압축 풀기

이미지 파일을 압축하는 잘 알려진 방법 중 하나는 1987년 CompuServe가 만든 GIF(Graphics Interchange Format) 인코딩이다. 여기서는 알파벳 문자열에 적용한 간단한 버전을 다룬다.

이 압축의 핵심은 문자열에 숫자 인코딩(이 문제에서는 10진수)을 부여하는 사전이다. 사전은 문자열에 나타날 수 있는 문자나 부분 문자열에 대한 대응으로 초기화된다. 예를 들어 알파벳 26자가 모두 나올 것으로 예상하면 사전은 처음에 (A, 00), (B, 01), (C, 02), ..., (Z, 25)를 저장한다. DNA 데이터를 압축한다면 (A, 0), (T, 1), (G, 2), (C, 3)의 네 항목만 저장한다. 초기 인코딩의 길이는 모든 항목에서 같다(첫 번째 예에서는 2자리, 두 번째 예에서는 1자리).

압축 알고리즘은 다음과 같이 진행된다.

1. 아직 압축되지 않은 부분 문자열의 접두사 중 사전에 있는 가장 긴 것을 찾아, 그 숫자 인코딩으로 치환한다.
2. 문자열의 끝에 도달하지 않았다면, 사전에 새 대응 (s, n)을 추가한다. 여기서 s는 방금 압축한 접두사에 그 다음 문자를 붙인 것이고, n은 아직 사용하지 않은 가장 작은 번호이다.

예를 들어 문자열 ABABBAABB를 (A, 0), (B, 1) 두 항목만 있는 사전으로 압축하는 과정은 아래와 같다.

최종 압축 결과는 01234이다.

규칙이 하나 더 있다. 치환에 쓰는 문자열의 길이는 항상 그 치환이 일어나는 시점에 사전에 있는 가장 긴 인코딩의 길이와 같다. 즉 위 사전에서 (s, 10) 형태의 항목이 추가되고 나면, 그 이후의 모든 치환은 2자리로 늘어난다(A는 00, B는 01, AB는 02, ...). (s', 100) 항목이 추가되면 그 시점부터 모든 치환이 3자리가 되고, 이런 식으로 계속된다. 따라서 더 긴 문자열 ABABBAABBAABAABAB는 0123402731이 아니라 01234027301로 인코딩된다.

이제 압축의 달인이 되었으니, 압축을 푸는 것을 해 보자!

각 테스트 케이스는 두 줄로 이루어진다. 첫 줄은 압축을 풀어야 할 숫자 문자열이다. 둘째 줄은 압축에 사용된 초기 사전으로, 먼저 사전 항목의 개수를 나타내는 양의 정수 n(1 <= n <= 100)이 오고, 이어서 n개의 알파벳 문자열이 온다. 이 문자열들 중 첫째는 0(또는 n > 10이면 00)과, 둘째는 1과, ... 짝지어진다.

마지막 테스트 케이스 다음에는 0 하나만 있는 줄이 온다.

각 테스트 케이스마다, 아래 형식으로 케이스 번호에 이어 압축을 푼 문자열을 한 줄에 출력한다. 모든 입력 문자열은 규칙에 맞게 압축된 것이다.

Case X: decompressed