import qualified Data.Map as Map;import Data.List(sortBy);import Data.Function(on)
lev m 0 j _ _=(m, j);lev m i 0 _ _=(m, i);lev m i j a b=if(i,j)`Map.member`m then(m, m Map.!(i,j))else(m', o)where(m1,o1)=lev m(i-1)(j-1)a b;(m2,o2)=lev m1 i(j-1)a b;(m3,o3)=lev m2(i-1)j a b;o=minimum[o1+(if a!!(i-1)==b!!(j-1)then 0 else 1),o2+1,o3+1];m'=Map.insert(i,j)o m3
lev' a b=snd$lev Map.empty(length a)(length b)a b
main=interact(\f->let l=lines f;h=head l in unlines$map snd$sortBy(compare`on`fst)$zip(map(lev' h)l)l)