1407. deMorse

Morse code is a way of encoding character strings using tones of two durations-short and long, separated by gaps. The short tones are called dots (denoted hereafter by *) and the long tones are called dashes (denoted hereafter by –). The exact duration of * is not specified (fast operators will use shorter durations), but the duration of – is equal to three *, and the duration of a gap is equal to one, three or seven *. In this problem, we consider encoded character strings over an alphabet of 27 characters-the lowercase letters a, b, c, . . . , z and the blank. Each lowercase letter is represented by a specific string of tones, given by the following Morse code table:

A lowercase letter is encoded by transmitting the tones representing it, separated by gaps of duration equal to one *. A word is encoded by transmitting its encoded letters, separated by gaps of duration equal to three *. Words are separated by a single blank transmitted as a gap of duration equal to seven *.

Input Format

Each line of input contains a (possibly empty) binary string representing the Morse encoding of a string of lowercase letters and blanks. Gaps separating tones within a letter appear as 0, gaps separating letters within a word appear as 000, and gaps separating words appear as 0000000. A * appears as 1 and a – appears as 111.

Output Format

For each line of input, output the string of lowercase letters and blanks it encodes.

1110001010101000100000001110111010111000101011100010100011101011101000111010111
11101010100010111010001110111011100010111011100011101
1010111010001110111011100011101010111
1011101110111000101011100011101110001011101110100010001110101
111000101010100010000000111010100011101110111000111011101

the quick
brown
fox
jumped
the dog