part m xxs@(_:xs) = last $ loop (length xxs - m) [[map (:[]) $ take i xxs] | i <- [1..m]] xs
  where 
    loop 0 xss _ = xss
    loop n (xs:xss) (y:ys) = loop (n-1) (step (update y xs) xss ys) ys
    step p [] _ = [p]
    step p (xs:xss) (y:ys) = p : step (update y xs ++ map ([y]:) p) xss ys
    update y xs = concatMap (go y) xs
      where 
        go y [] = []
        go y (x:xs) = ((y:x):xs) : map (x:) (go y xs)
main = print $ part 3 [1..5]

cGFydCBtIHh4c0AoXzp4cykgPSBsYXN0ICQgbG9vcCAobGVuZ3RoIHh4cyAtIG0pIFtbbWFwICg6W10pICQgdGFrZSBpIHh4c10gfCBpIDwtIFsxLi5tXV0geHMKICB3aGVyZSAKICAgIGxvb3AgMCB4c3MgXyA9IHhzcwogICAgbG9vcCBuICh4czp4c3MpICh5OnlzKSA9IGxvb3AgKG4tMSkgKHN0ZXAgKHVwZGF0ZSB5IHhzKSB4c3MgeXMpIHlzCiAgICBzdGVwIHAgW10gXyA9IFtwXQogICAgc3RlcCBwICh4czp4c3MpICh5OnlzKSA9IHAgOiBzdGVwICh1cGRhdGUgeSB4cyArKyBtYXAgKFt5XTopIHApIHhzcyB5cwogICAgdXBkYXRlIHkgeHMgPSBjb25jYXRNYXAgKGdvIHkpIHhzCiAgICAgIHdoZXJlIAogICAgICAgIGdvIHkgW10gPSBbXQogICAgICAgIGdvIHkgKHg6eHMpID0gKCh5OngpOnhzKSA6IG1hcCAoeDopIChnbyB5IHhzKQptYWluID0gcHJpbnQgJCBwYXJ0IDMgWzEuLjVd