main=interact$unlines.foldr(\x y->x:f(==x)y++f(/=x)y)[].lines
f=filter