Morse Code -- Problem J (15 points)

Morse Code was invented to allow the transmission of messages electrically, before telephones were invented. Only two sorts of symbols were used, a "dot", represented as a "." when written, which was a short signal, and a "dash", represented as a "-" when written, which was a long signal. Each letter of the alphabet was given a code in terms of dots and dashes, according to the following table (only upper-case letters were encoded):

    A .-     E .     I ..    M --    Q --.-  U ..-   Y -.--
    B -...   F ..-.  J .---  N -.    R .-.   V ...-  Z --..
    C -.-.   G --.   K -.-   O ---   S ...   W .--
    D -..    H ....  L .-..  P .--.  T -     X -..-

When transmitting signals in this code digitally, each dot is represented by a single 1 bit and each dash by three 1 bits. Gaps within a letter, between the dots and dashes, are represented by a single 0 bit, and gaps between letters by three 0 bits. Gaps between words are represented by five 0 bits. Thus the words "TRY THIS" are encoded:

    1110001011101000111010111011100000111000101010100010100010101

In a valid message, there will always be at least one 0 at the beginning and end.

Because of random disturbances in the transmission line, errors can enter a message. Each message received is analysed to find the maximum number of bits, starting from the left end, which form a valid message. For example, the message 111010 is completely invalid because it has no 0 at the front, and so is 01111010 because there is no 0 after the first 3 ones, while 011101 has 01110 as its largest valid message.

Input will be from a file PROBLEMJ.DAT, and will consist of lines of at most 70 0's and 1's, each containing a message in Morse Code. There will be an arbitrary number of 0 bits before the first 1 bit in each message, and after the last bit (there must be at least one zero bit at each end). The file will be terminated by a line containing a single #.

Output, which must be written to standard output (the screen), must consist of lines containing the decoded messages, one output line for each input line. If, when decoding a line, the pattern of 0's and 1's on a line is not valid (for example, you encounter four 0's then a 1), then you must write the part of message forming the largest valid message, followed by a ?.

Example Input

0000000000111000111011101110000010111011100010100011101000000
011101000111011101010000010100010101001011101010001110111000010
011110000000000000000000

Example Output

TO WIN
NZ IS?
?