Decompressing in a GIF

One well-known method for compressing image files is the Graphics Interchange Format (GIF) encoding, created by CompuServe in 1987. Here is a simplified version applied to strings of alphabetic characters.

Central to this compression is a dictionary that assigns numeric encodings (base-10 numbers for this problem) to strings of characters. The dictionary is initialized with mappings for the characters or substrings that may appear in the string. For example, if we expect all 26 letters, the dictionary initially stores (A, 00), (B, 01), (C, 02), ..., (Z, 25). For DNA data it stores only four entries: (A, 0), (T, 1), (G, 2), and (C, 3). The length of every initial encoding is the same (2 digits in the first example, 1 digit in the second).

The compression algorithm works as follows:

1. Find the longest prefix of the still-uncompressed part of the string that is in the dictionary, and replace it with its numeric encoding.
2. If the end of the string has not been reached, add a new mapping (s, n) to the dictionary, where s is the prefix just compressed plus the next character after it in the string, and n is the smallest number not yet used in the dictionary.

For example, starting from the string ABABBAABB with a dictionary of the two entries (A, 0) and (B, 1), the compression proceeds as shown below.

The final compressed string is 01234.

There is one more rule: the replacement strings are always the size of the longest encoding in the dictionary at the time the replacement occurs. So with the dictionary above, once an entry of the form (s, 10) is added, every later replacement must be expanded to 2 digits (A becomes 00, B becomes 01, AB becomes 02, and so on); once an entry (s', 100) is added, every replacement from then on becomes 3 digits, and so on. Thus the longer string ABABBAABBAABAABAB is encoded as 01234027301, not 0123402731.

Now that you are an expert at compressing, it is time to decompress!

Each test case consists of two lines. The first line is a string of digits to decompress. The second line is the initial dictionary used during compression: it begins with a positive integer n (1 <= n <= 100), the number of dictionary entries, followed by n alphabetic strings. The first of these strings is paired with 0 (or 00 if n > 10), the second with 1, and so on.

The last test case is followed by a line containing a single 0.

For each test case, output one line containing the case number (in the format shown below) followed by the decompressed string. Every input string was legally compressed.

Case X: decompressed