Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to one character is not the prefix of code assigned to any other character. Let us understand prefix codes with an example. Let there be four characters a, b, c and d, and their corresponding variable length codes be 00,01,0 and 1. This coding leads to ambiguity because code assigned to c is the prefix of codes assigned to a and b. Suppose if the compressed bit stream is 0001, the de-compressed output may be "coco" or "ccb" or "acd" or "ab" which is ambigious and we are not are of the correct output. The main application of Huffman coding is to remove this ambiguity To remove this ambiguity we use Huffman Coding to make sure that there is no amo-quity when decoding the generated bitstream Now you are given an array of characters along with their respective frequency and your task is to generate Huffman codes for each of the character so that there is no ambiguity and decoding leads to a correct answer.

Input format
First fine: T (Number of test cases)
The first line of each test case contains an integer N represents the number of character in the array
The next line contains N distinct space separated characters
The next line contains the frequency of each character respectively

Output format
For each test case, print the Huffman code for each character of the character array.
Constraints
1 ≤ T ≤ 10^3
1 ≤ N ≤ 26
a ≤ each character of character array ≤ z
1 ≤ frequency of each character ≤ 10^5

Sample Input
1
4
a b c d
5 7 2 9
Sample Output
d: 0
b: 10
c: 110
a: 111

Answer rating: 100% (QA)

To generate Huffman codes for a given set of characters and their frequencies you can follow these s... View the full answer