m@main=getLine>>=putStrLn.f.words>>m
f[a:b,c:d]=max(a:f[b,c:d])$c:f[a:b,d]
f l=l>>=id