Bluffman Encryption

3.7

9 votes
Problem

The Kraken lives!

Tragedy has struck the trade world since news has spread of the rise of the Kraken that terrorizes the Mediterranean Sea. Any ship that attempts to cross this strait is torn apart by the mighty tentacles of the beast and all its occupants face a fate worse than death.

You have chanced upon a map that claims to offer you a safe alternate passage to your destination across the sea. However, the map is completely incomprehensible. Luckily, your partner has found a ancient document that shows you how to make sense of the map.

Apparently, some old chap named Davy Jones had discovered this safe route when the Kraken had last awoken. He was unable to explain the route graphically, so he came up with a textual form. But the textual form turned out to take up too many bytes on the sub-digital piece of paper. (The technology is now lost and the paper lost its digital-ness over time)

So the brilliant Davy Jones came up with a method to compress the text based on the frequency of letters in it. His plan was to assign a binary code (consisting of 0's and 1's) to each letter appearing in the string. The length of the binary code would be shorter for characters appearing more frequently in the string and vice versa. Therefore, the string would become compressed as each letter took up less than the normal 8 bits of data and also, more frequent characters took up the minimal amount of space. Also, he made sure that no code for any character appeared as the prefix of a code for another character, to prevent ambiguity while decoding. Decoding would be facilitated by providing the appearing characters and their frequencies in the original string along with the encrypted string. Thus the code mapping could be reconstructed. Davy Jones assigned the job of creating the map to his cartographer.

However, alas, it was a Friday and the cartographer, heavily drunk on cheap rum, messed up the whole map.

Instead of the intended method, he assigned binary codes in the opposite order of frequency, that is, more frequent characters ended up with longer codes and vice versa. Also, the character frequencies provided for decoding have been given relative to the least frequency. (i.e. the least frequent character gets a frequency value 0 and the rest are the difference between their actual values and the actual minimum frequency, see example below) (Read the notes below before attempting)

Since there was no time to fix this mistake, Davy Jones published this map, the last remaining copy of which has ended up with you.

Your job is to decrypt the map and discover the safe passage you require to bypass the Kraken.


Input Format

The first line contains T, the number of test cases. For each test case, the first line contains N, the number of distinct characters appearing in the encrypted string. The next N lines contain the character and the frequency of that character, separated by a space. (Characters will be given in an alphabetical order) Finally, the next line contains the encrypted string.


Output Format

For each test case, output the decrypted string in separate lines.


Constraints:

  • 1<=T<=255
  • 1<=N<=26
  • Input encrypted string length <= 1200 characters
  • The output string will consist of only lowercase English characters (a-z).


Notes:

  • Higher frequency characters get assigned longer and higher valued binary codes than lower frequency characters.
  • In case of a tie in frequency, the character which appears before the other in the alphabet gets assigned the lower valued code.
  • 1 is considered a higher valued code than 0.
  • No code for any character is allowed to be the prefix of the code for another character. (i.e. 0 for 'a' and 01 for 'b' is not allowed as 0 is a prefix for 01)
  • The output string can have 1 to 95 characters (both inclusive).
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
4
a 3
b 0
c 1
d 0
111111111111011011010

Here, the binary codes for the letters, calculated from the frequencies are: b: 0 d: 10 c: 110 a: 111

Notice how none of them are the prefix of any other code.

Decrypting the input string according to the calculated codes gives us the solution string "aaaabccd".

Editor Image

?