import Data.Function
import qualified Data.List as L
import qualified Data.Map  as M

sp :: Char
sp = '_'

alignColumn :: [String] -> [String]
alignColumn = L.transpose . f . L.transpose . addsp
    where
      addsp xss = map add xss
          where maxlen = foldr (\x a -> if length x > a then length x else a) 0 xss
                add xs = xs ++ replicate (maxlen - length xs) sp
      f [] = []
      f xss = g $ do
          is <- groupOfIndex $ head xss
          let (ys:yss) = insertSP xss is
          return $ ys : f yss
      g [] = []
      g xs = L.minimumBy (compare `on` length) xs

insertSP :: [String] -> [Int] -> [String]
insertSP xss1 is = f xss1 pre
    where
      pre = zipWith (\k _ -> if elem k is then Nothing else Just sp) [0..] (head xss1)
      f [] cs
          | all (== Nothing) cs = []
          | otherwise = foldr (\x acc -> maybe sp id x : acc) [] cs : []
      f (xs:xss) cs = (map fst ys) : f xss (map snd ys)
          where
            ys = zipWith g xs cs
                where
                  g x Nothing = (x, Nothing)
                  g x (Just c) = (c, Just x)

groupOfIndex :: String -> [[Int]]
groupOfIndex xs = map (spi++) . M.elems . fst . foldl f (M.empty, 0) $ xs
    where
      spi = L.findIndices (==sp) xs
      f (acc,i) x
          | x == sp = (acc, i+1)
          | otherwise = (M.insertWith (++) x [i] acc, i+1)

main :: IO ()
main = do
    run ["1","1"]
    run ["1","2"]
    run ["12", "21"]
    run ["11", "12"]
    run ["113", "114"]
    run ["123", "134"]
    run ["1212", "1322", "1122"]
    run ["123", "113", "1323"]
    run ["1234", "4321", "1122"]
    -- run ["12121313432121233", "21322312443213443"]
    where
      run xs = do
          mapM_ putStrLn xs
          putStrLn . unlines $ alignColumn xs

aW1wb3J0IERhdGEuRnVuY3Rpb24KaW1wb3J0IHF1YWxpZmllZCBEYXRhLkxpc3QgYXMgTAppbXBvcnQgcXVhbGlmaWVkIERhdGEuTWFwICBhcyBNCgpzcCA6OiBDaGFyCnNwID0gJ18nCgphbGlnbkNvbHVtbiA6OiBbU3RyaW5nXSAtPiBbU3RyaW5nXQphbGlnbkNvbHVtbiA9IEwudHJhbnNwb3NlIC4gZiAuIEwudHJhbnNwb3NlIC4gYWRkc3AKICAgIHdoZXJlCiAgICAgIGFkZHNwIHhzcyA9IG1hcCBhZGQgeHNzCiAgICAgICAgICB3aGVyZSBtYXhsZW4gPSBmb2xkciAoXHggYSAtPiBpZiBsZW5ndGggeCA+IGEgdGhlbiBsZW5ndGggeCBlbHNlIGEpIDAgeHNzCiAgICAgICAgICAgICAgICBhZGQgeHMgPSB4cyArKyByZXBsaWNhdGUgKG1heGxlbiAtIGxlbmd0aCB4cykgc3AKICAgICAgZiBbXSA9IFtdCiAgICAgIGYgeHNzID0gZyAkIGRvCiAgICAgICAgICBpcyA8LSBncm91cE9mSW5kZXggJCBoZWFkIHhzcwogICAgICAgICAgbGV0ICh5czp5c3MpID0gaW5zZXJ0U1AgeHNzIGlzCiAgICAgICAgICByZXR1cm4gJCB5cyA6IGYgeXNzCiAgICAgIGcgW10gPSBbXQogICAgICBnIHhzID0gTC5taW5pbXVtQnkgKGNvbXBhcmUgYG9uYCBsZW5ndGgpIHhzCgppbnNlcnRTUCA6OiBbU3RyaW5nXSAtPiBbSW50XSAtPiBbU3RyaW5nXQppbnNlcnRTUCB4c3MxIGlzID0gZiB4c3MxIHByZQogICAgd2hlcmUKICAgICAgcHJlID0gemlwV2l0aCAoXGsgXyAtPiBpZiBlbGVtIGsgaXMgdGhlbiBOb3RoaW5nIGVsc2UgSnVzdCBzcCkgWzAuLl0gKGhlYWQgeHNzMSkKICAgICAgZiBbXSBjcwogICAgICAgICAgfCBhbGwgKD09IE5vdGhpbmcpIGNzID0gW10KICAgICAgICAgIHwgb3RoZXJ3aXNlID0gZm9sZHIgKFx4IGFjYyAtPiBtYXliZSBzcCBpZCB4IDogYWNjKSBbXSBjcyA6IFtdCiAgICAgIGYgKHhzOnhzcykgY3MgPSAobWFwIGZzdCB5cykgOiBmIHhzcyAobWFwIHNuZCB5cykKICAgICAgICAgIHdoZXJlCiAgICAgICAgICAgIHlzID0gemlwV2l0aCBnIHhzIGNzCiAgICAgICAgICAgICAgICB3aGVyZQogICAgICAgICAgICAgICAgICBnIHggTm90aGluZyA9ICh4LCBOb3RoaW5nKQogICAgICAgICAgICAgICAgICBnIHggKEp1c3QgYykgPSAoYywgSnVzdCB4KQoKZ3JvdXBPZkluZGV4IDo6IFN0cmluZyAtPiBbW0ludF1dCmdyb3VwT2ZJbmRleCB4cyA9IG1hcCAoc3BpKyspIC4gTS5lbGVtcyAuIGZzdCAuIGZvbGRsIGYgKE0uZW1wdHksIDApICQgeHMKICAgIHdoZXJlCiAgICAgIHNwaSA9IEwuZmluZEluZGljZXMgKD09c3ApIHhzCiAgICAgIGYgKGFjYyxpKSB4CiAgICAgICAgICB8IHggPT0gc3AgPSAoYWNjLCBpKzEpCiAgICAgICAgICB8IG90aGVyd2lzZSA9IChNLmluc2VydFdpdGggKCsrKSB4IFtpXSBhY2MsIGkrMSkKCm1haW4gOjogSU8gKCkKbWFpbiA9IGRvCiAgICBydW4gWyIxIiwiMSJdCiAgICBydW4gWyIxIiwiMiJdCiAgICBydW4gWyIxMiIsICIyMSJdCiAgICBydW4gWyIxMSIsICIxMiJdCiAgICBydW4gWyIxMTMiLCAiMTE0Il0KICAgIHJ1biBbIjEyMyIsICIxMzQiXQogICAgcnVuIFsiMTIxMiIsICIxMzIyIiwgIjExMjIiXQogICAgcnVuIFsiMTIzIiwgIjExMyIsICIxMzIzIl0KICAgIHJ1biBbIjEyMzQiLCAiNDMyMSIsICIxMTIyIl0KICAgIC0tIHJ1biBbIjEyMTIxMzEzNDMyMTIxMjMzIiwgIjIxMzIyMzEyNDQzMjEzNDQzIl0KICAgIHdoZXJlCiAgICAgIHJ1biB4cyA9IGRvCiAgICAgICAgICBtYXBNXyBwdXRTdHJMbiB4cwogICAgICAgICAgcHV0U3RyTG4gLiB1bmxpbmVzICQgYWxpZ25Db2x1bW4geHMK