Lesson 13

Programming problem.

Restore the string from its code and the prefix-free character codes.

The first line of the input file contains two integers \(k\) and \(l\) separated by a space—the number of distinct letters in the string and the size of the resulting encoded string, respectively. The next \(k\) lines contain the letter codes in the format «letter: code». No code is a prefix of another. Letters can be listed in any order. Only lowercase Latin letters may appear as letters; each of these letters appears at least once in the string. Finally, the last line contains the encoded string.

The original string and all codes are non-empty. The given code is such that the encoded string has the smallest possible size.

In the first line of the output file, print the string \(s\). It should consist of lowercase Latin letters. It is guaranteed that the length of the correct answer does not exceed \(10^{4}\).

1 1
a: 0
0

a