main=interact$(>>=unlines).reverse.scanr((.("":)).map.(:))[]