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