main=interact$unlines.scanl1(\x y@(a:b)->max(a:x!b)$y!x).lines
x!y=do(a,b)<-zip(y>>x)y;[a,b]