Lib.hs

module Main where

import Data.List (sort, sortBy)
import Control.Applicative
import Control.Monad (forM, replicateM_)
import Data.Set (Set)
import qualified Data.Set as Set
import qualified Data.Sequence as Seq
import qualified Data.Vector (freeze)
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM


--------------------------------------------------------------------------------
-- Queue Implementation

type Queue a = Seq.Seq a
  
emptyQueue = Seq.empty  

enqueue a queue = a Seq.<| queue

dequeue queue = 
  case Seq.viewl queue of
    Seq.EmptyL ->
      Nothing

    a Seq.:< queue1 ->
      Just (a, queue1)

nullQueue = Seq.null  

--------------------------------------------------------------------------------

compareSets :: Ord a => Set a -> Set a -> Ordering
compareSets a b =
  if Set.size a > Set.size b then
    GT
  else if Set.size a < Set.size b then
    LT
  else
    compare (Set.toAscList a) (Set.toAscList b)

minSet a b =
  case compareSets a b of
    GT ->
      b
    LT ->
      a
    EQ -> 
      a

reverseFactorization :: Int -> [Int] -> Maybe (Set Int)
reverseFactorization total numbers =
  let
    queue0 =
      enqueue (1, Set.fromList [1]) emptyQueue

    step :: (Set Int, Maybe (Set Int)) -> Queue (Int, Set Int) -> (Set Int, Maybe (Set Int))
    step (visited, result) queue =
      case dequeue queue of
        Nothing ->
          (visited, result)

        Just ((pathTotal, pathSteps), queue1) ->
          if pathTotal == total then
            step (visited
                 , (minSet
                    <$> result
                    <*> pure pathSteps)
                   <|> pure pathSteps) queue1

          else
            let
              queue2 = 
                  foldr (\number queueAcc ->
                           let
                             number1 = number * pathTotal
                           in
                             if number1 > total || Set.member number1 visited then
                               queueAcc
                             else
                               enqueue (number1, Set.insert number1 pathSteps) queueAcc)
                        queue1
                        numbers

              visited1 =
                Set.insert pathTotal visited
            in
              step (visited1, result) queue2
  in
    snd $ step (Set.fromList [1], Nothing) queue0

main :: IO ()
main = do
  (n:k:_) <- (map read . words) <$> getLine
  numbers <- (sort . map read . take k . words) <$> getLine
  case reverseFactorization n numbers of
    Nothing ->
      print (-1)
    Just result ->
      putStrLn . unwords . map show . Set.toAscList $ result