Huffman Encoding

Huffman coding is an elegant text-compression algorithm designed by David Huffman in 1952.

The core idea is to assign each character a binary code (a sequence of 0s and 1s). These codes are prefix-free: no character's code is ever a prefix of another character's code.

A convenient way to build prefix-free codes is to place the characters at the leaves of a binary tree, labeling every left edge 0 and every right edge 1. The path from the root down to a leaf spells out the code of the character stored at that leaf. For example, the binary tree below defines prefix-free codes for the characters {A, B, C, D, E}:

Here A is encoded as 00, B as 01, C as 10, D as 110, and E as 111.

Because the codes are prefix-free, any concatenation of them can be decoded back into the original characters in exactly one way.

Given a Huffman code (a set of characters together with their binary codes) and a binary sequence, decode the binary sequence back into its characters.

The first line contains an integer $k$ ($1 \le k \le 20$), the number of characters. Each of the next $k$ lines contains one character, a single space, and the binary code (of length at most $10$) assigned to that character. Every character is a letter (a--z or A--Z), and the given codes are guaranteed to be prefix-free.

The following line contains the binary sequence to decode. This sequence is a valid concatenation of the given codes and contains at most $250$ binary digits.

Output, on a single line, the characters that the binary sequence decodes to.