PROGRAMMING:Huffman tree
Write a Huffman coding and decoding program. For a piece of text, the Huffman tree is constructed according to the frequency of characters in the text, the Huffman code of each character is given, and the text size before and after coding is calculated.
In order to ensure the uniqueness of the constructed Huffman tree, this paper makes the following restrictions:
1. When selecting the two binary trees with the smallest weight of root node, the one with the smaller weight is selected as the left subtree.
2. If the weights of the root nodes of multiple binary trees are equal, the first one will be the left subtree, and the second one will be the right subtree. Specifically, I) for a single node binary tree, the first one with the corresponding letter of the root node appears in the text is preferred. If the text is CBA, all three letters appear once, but C appears first in the text and B appears second, so C is selected as the left subtree, B as the right subtree. II) for a non single node binary tree, the generated binary tree is taken as the left subtree, and the generated binary tree is taken as the right subtree. If the root weights of single node and non single node binary tree are equal, single node binary tree is preferred.
3. When generating Huffman code, the left branch of Huffman tree is marked as 0, and the right branch is marked as 1.
###Input format:
The input is 3 lines. The first line is a string, which contains no more than 5000 characters and at least two different characters, each of which is A-Z lowercase letter. The second and third lines are two strings composed of 0 and 1, representing the Huffman code to be decoded.
###Output format:
Output two integers separated by spaces in the first line, which are respectively the size of the text before and after compression, in bytes. One character occupies 1 byte, and eight binary bits occupy 1 byte. If the compressed text is less than 8 bits, it will be counted as 1 byte. The output starts from the second line, and the Huffman code of one character per line is output according to the increasing number of characters appearing in the text. If multiple characters appear the same number of times, they are arranged in the order of their appearing in the text. The format of each line is "letter: Code". The last two lines are two lines of string, indicating the decoding result. If decoding fails, invalid will be output.
###Input example:
```in
cbaxyyzz
0100
011
```
###Output example:
```out
8 3
c:100
b:101
a:110
x:111
y:00
z:01
zy
INVALID
```
answer：If there is no answer, please comment
In order to ensure the uniqueness of the constructed Huffman tree, this paper makes the following restrictions:
1. When selecting the two binary trees with the smallest weight of root node, the one with the smaller weight is selected as the left subtree.
2. If the weights of the root nodes of multiple binary trees are equal, the first one will be the left subtree, and the second one will be the right subtree. Specifically, I) for a single node binary tree, the first one with the corresponding letter of the root node appears in the text is preferred. If the text is CBA, all three letters appear once, but C appears first in the text and B appears second, so C is selected as the left subtree, B as the right subtree. II) for a non single node binary tree, the generated binary tree is taken as the left subtree, and the generated binary tree is taken as the right subtree. If the root weights of single node and non single node binary tree are equal, single node binary tree is preferred.
3. When generating Huffman code, the left branch of Huffman tree is marked as 0, and the right branch is marked as 1.
###Input format:
The input is 3 lines. The first line is a string, which contains no more than 5000 characters and at least two different characters, each of which is A-Z lowercase letter. The second and third lines are two strings composed of 0 and 1, representing the Huffman code to be decoded.
###Output format:
Output two integers separated by spaces in the first line, which are respectively the size of the text before and after compression, in bytes. One character occupies 1 byte, and eight binary bits occupy 1 byte. If the compressed text is less than 8 bits, it will be counted as 1 byte. The output starts from the second line, and the Huffman code of one character per line is output according to the increasing number of characters appearing in the text. If multiple characters appear the same number of times, they are arranged in the order of their appearing in the text. The format of each line is "letter: Code". The last two lines are two lines of string, indicating the decoding result. If decoding fails, invalid will be output.
###Input example:
```in
cbaxyyzz
0100
011
```
###Output example:
```out
8 3
c:100
b:101
a:110
x:111
y:00
z:01
zy
INVALID
```
answer：If there is no answer, please comment