main=interact$unlines.reverse.init.scanr(#)[]
a#b=a:b++[a]