main=interact$unlines.f.lines
f(x:y)=x:s(==x)y++f(s(/=x)y);f[]=[]
s=filter