Fragment Reassembly

Time limit1sMemory limit128 MB

Summary

Arrange the given text fragments so neighbors share an exact overlap and print the joined text in lines of at most 72 characters.

Level: Hard8 of 10
Topics: Backtracking, String matching, Graph
Solved: No attempts yet

Problem

A secret document was shredded into overlapping text fragments. Read the fragment lists and reassemble them by matching overlaps.

Input

Several problems follow. Each problem has 1 to 20 fragment lines terminated by a line containing only #. Each line has 1 to 72 printable characters; words are separated by a single space. # marks the end of a problem and of the whole input. Duplicate fragments may appear.

Output

For each problem, print any arrangement of the fragments where every input fragment appears and adjacent fragments overlap exactly. Each output line has at most 72 characters. Break lines only at word boundaries and do not print the separating space at a break. Do not insert blank lines between problems.

Examples1

Example 1

Input

they chose Avant
from the regular text.
For headings, they
stands out nicely from
sans-serif font that stands
Avant Garde, a sans-serif
from the regular text.
#
a b r a
c a d a b r a
#
a b r a
c a d a b r a
r a c
#
#

Expected output

For headings, they chose Avant Garde, a sans-serif font that
stands out nicely from the regular text.
c a d a b r a
c a d a b r a c