module Main where
--------------------------------------------------------------------------------
toCandetat :: Char -> [Char]
toCandetat '0' = "oqz"
toCandetat '1' = "ij"
toCandetat '2' = "abc"
toCandetat '3' = "def"
toCandetat '4' = "gh"
toCandetat '5' = "kl"
toCandetat '6' = "mn"
toCandetat '7' = "prs"
toCandetat '8' = "tuv"
toCandetat '9' = "wxy"
toCandetat n = error "unkown numb"
--------------------------------------------------------------------------------
convertToCandedat :: String -> [String]
convertToCandedat = map toCandetat
--------------------------------------------------------------------------------
testWord :: String -> [String] -> Bool
testWord str can = and $ zipWith elem str  can
--------------------------------------------------------------------------------
loop :: [String] -> String -> String
loop []     acc = tail acc
loop ["-1"] acc = tail acc
loop in_str acc = loop next (acc ++ "\n" ++ fixPart)
  where
   fixPart         = if part == "" then "No soluton." else part
   part            = partSolve test cand []
   (numb:count:xs) = in_str
   cand            = convertToCandedat numb
   int_count       = read count
   (test, next)    = splitAt int_count xs
--------------------------------------------------------------------------------
partSolve :: [String] -> [String] -> String -> String
partSolve []     []  acc                  = tail acc
partSolve (x:xs) can acc | testWord x can = skipX  ++ nextXs
                         | otherwise      = partSolve xs can             acc
  where
    lenX   = length x
    skipX  = partSolve xs can             acc
    nextXs = partSolve xs (drop lenX can) (acc ++ " " ++ x)
partSolve _      _   _                    = ""
--------------------------------------------------------------------------------
main :: IO ()
main = do
  in_str <- getContents
  putStr $ loop (words in_str) []
--------------------------------------------------------------------------------