Given a string s of length at most 104 over the alphabet of

Question

Code problem: Huffman encoding

Given a string s of length at most 104 over the alphabet of lower case latin letters. In the first line output the number k of different symbols and the length l of a binary encoding. In each of the next k lines output a binary code of a symbol in the form ": ". In the last line output the encoded string. 

Sample Input 1:
a

Sample Output 1:
1 1
a: 0
0

Sample Input 2:
abacabad

Sample Output 2:
4 14
a: 0
b: 10
c: 110
d: 111
01001100100111

Memory Limit: 256 MB
Time Limit: 5 seconds

Huffman decoding

Given a Huffman encoding e of a string s output s.

The first line of the input contains the number k of different symbols in s and the length l of the encoding e of s. Each of the following k lines define a binary encoding of a symbol in the format ": ". None of the codes is a prefix of another. The symbols are lower case latin letters. Each of the given k symbols appears in s. The last line of the input contains the encoding e. Output the string s. The length of s is at most 104.

Sample Input 1:
1 1
a: 0
0
Sample Output 1:
a

Sample Input 2:
4 14
a: 0
b: 10
c: 110
d: 111
01001100100111
Sample Output 2:
abacabad

Memory Limit: 256 MB
Time Limit: 5 seconds