Xenosemantics

Contact with extra-terrestrial intelligence has been made at last! A stream of messages has been discovered, apparently emanating from Procyon IV. After intensive study by the world's best xenosemanticists, the following definite conclusions about the format of the messages have been reached.

The messages are streams of bits divided into groups of 8. The meaningful parts of a message map onto the lowercase alphabet, although other characters sometimes intervene. Letters are organised into words separated by spacer letters. The spacer letter varies within a message, but a word delimited by a particular spacer pair does not contain that spacer letter inside it. In addition, the message is conceptually bounded by a pair of joker letters (or wild spacers) that can match any letter.

For example, the message segment xwrxwtx contains 3 words: wr, wt, and rx. The string wrxwt is not a word in this segment. If this segment appeared at the start of a message, then xw and xwrxw could also be words. The words wr and rx overlap, while wt does not overlap any word in this segment.

While a word contains the same letters each time it appears in one message, the order of the letters may vary between occurrences of the same word. In other words, two occurrences with the same multiset of letters are the same word.

A message contains many words that carry no meaning (like "err" or "umm" in English). A true word is a word that satisfies all of the following:

• it contains at least 2 and at most 250 letters,
• it overlaps (shares at least one position with) an occurrence of another true word, and
• it is repeated somewhere in the message (it occurs at least twice, possibly with its letters in a different order).

In the example above, wr and rx would both be true words if wr or rw, and rx or xr, occurred as words elsewhere in the message. The word wt would be a true word if wt or tw occurred elsewhere in the message while overlapping another true word.

Write a program that reads messages and prints, for each message, the list of distinct true words it contains. Print each true word using the spelling of its first occurrence, in the order the words first appear in the message. If the first occurrences of two words overlap, the word whose first occurrence finishes first (ends at an earlier position) comes first. Remember that both the start and the end of the message count as spacer letters. A message contains up to 1000 letters.

The input consists of one or more messages. Each message consists of one or more lines. Each line is at most 60 characters long and contains a mixture of lowercase letters and other characters. If the last character of a line is a dash (-), the message continues on the next line. All characters other than the lowercase letters a to z form no part of the message. The input is terminated by a line consisting of a single #.

For each message, print its true words in the order described above, one word per line. Terminate the list for each message with a line consisting of a single \*.