{-# LANGUAGE BangPatterns #-} import Control.Monad import Control.Monad.ST import Control.Monad.State import Control.Monad.Fix import Data.Bits import Data.Char import Data.Coerce import Data.Word import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM main :: IO () main = do n <- readLn :: IO Int total <- readLn :: IO Int as <- seqInput n let dp = solve n total as dpt = dp VU.! total rep (n - 1) $ \i -> do if (dpt .>>. (n - 2 - i)) `mod` 2 == 1 then putStr "*" else putStr "+" putStrLn "" solve :: Int -> Int -> VU.Vector Int -> VU.Vector Int solve n total as = VU.create $ do dp <- VUM.replicate (total + 1) (1 .<<. n) VUM.unsafeWrite dp (as VU.! 0) 0 rep1 n $ \i -> do dp2 <- VUM.replicate (total + 1) (1 .<<. n) :: ST s (VUM.STVector s Int) rep (total + 1) $ \j -> do dpj <- VUM.unsafeRead dp j unless (dpj == (1 .<<. n)) $ do when (j + as VU.! i <= total) $ VUM.unsafeModify dp2 (min (dpj * 2)) (j + as VU.! i) when (j * as VU.! i <= total) $ VUM.unsafeModify dp2 (min (dpj * 2 + 1)) (j * as VU.! i) VUM.unsafeMove dp dp2 return dp infixl 8 .>>., .<<. (.>>.) :: Bits b => b -> Int -> b (.>>.) = unsafeShiftR {-# INLINE (.>>.) #-} (.<<.) :: Bits b => b -> Int -> b (.<<.) = unsafeShiftL {-# INLINE (.<<.) #-} rep :: Monad m => Int -> (Int -> m ()) -> m () rep n = flip VFSM.mapM_ (stream 0 n) {-# INLINE rep #-} rep1 :: Monad m => Int -> (Int -> m ()) -> m () rep1 n = flip VFSM.mapM_ (stream 1 n) {-# INLINE rep1 #-} stream :: Monad m => Int -> Int -> VFSM.Stream m Int stream l r = VFSM.Stream step l where step x | x < r = return $ VFSM.Yield x (x + 1) | otherwise = return VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] stream #-} type Parser a = StateT BSC8.ByteString Maybe a runParser :: Parser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString) runParser = runStateT {-# INLINE runParser #-} int :: Parser Int int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace {-# INLINE int #-} seqInput :: Int -> IO (VU.Vector Int) seqInput n = VU.unfoldrN n (runParser int) <$> BSC8.getLine {-# INLINE seqInput #-}