One simple way to compress messages consisting of restricted character data is to use a minimal number of bits to represent each character and to pack the resulting bit strings into bytes. If the character data is restricted to uppercase letters, spaces and the punctuation symbols ". ? , ; '", we can represent each character as a 5-bit unsigned number. In this representation A through Z are associated with the numbers 1 through 26, respectively; space is associated with 0; and the punctuation symbols use the associations period - 27, question mark - 28, comma - 29, semicolon - 30, and apostrophe - 31. For example, consider the message:
ISN'T THIS AN ODD MESSAGE?
The characters are converted to numbers as above.
9 19 14 31 20 0 20 8 9 ... 19 1 7 5 28 I S N ' T T H I S A G E ?
These are then placed into bytes as shown below; underlining and hyphens indicate which bits are part of each byte.
9 19 14 31 20 0 7 5 28 01001 10011 01110 11111 10100 00000 ... 00111 00101 11100 000000 _________----------_________------- _____ ---------_________
After the last 5-bit value, the remainder of the byte is filled out with zero bits. So, the final compressed message in hexadecimal looks like this:
4CDDFA02884CC01701E4201A59CC272F00
Your task is to read in the hexadecimal character representation of a compressed message and to display the decompressed (original) message. The input consists of a single string of hexadecimal digits. Thus, if the input consists of the hexadecimal string above, your program should display ISN'T THIS AN ODD MESSAGE?
Even if the input is long, such as below, it is still a single record compressed message.
2D8AE04E920B8E503E40ABAB3A8580BBE449818959413AC0B218589348274B133A2465C41216048F1A5F5981A1C81E31D6404B81441665034B3984E59EC000B89D05D19039F4E0
The only end of line is after the last zero. Your program should display the following (with line break allowed anywhere). Original messages may consist of up to 255 characters.
EVEN STRANGE OR UNUSUAL WORDS LIKE SUPERCALIFRAGILISTICEXPIALADOCIOUS MAY OCCUR IN THESE MESSAGES. AND, WHY NOT?