{-# LANGUAGE FlexibleInstances #-}
--FlexibleInstances чтоб можно было Show (Exp Rational) объявить

import Data.List hiding (permutations)
import Control.Monad
import Data.Ratio

data Exp a = Plus (Exp a) (Exp a) | Minus (Exp a) (Exp a) |
             Mul (Exp a) (Exp a) | Div (Exp a) (Exp a) | Number a

--объявили рекурсивный тип, описывающий выражения
instance (Show (Exp Rational)) where
  show exp = case exp of
    Number a -> show $ numerator a `div` denominator a
    Plus a b -> "(" ++ show a ++ "+" ++ show b ++ ")"
    Minus a b -> "(" ++ show a ++ "-" ++ show b ++ ")"
    Mul a b -> "(" ++ show a ++ "*" ++ show b ++ ")"
    Div a b -> "(" ++ show a ++ "/" ++ show b ++ ")"


--вычисляет выражение
eval exp = case exp of
  Number a -> a
  Plus a b -> eval a + eval b
  Minus a b -> eval a - eval b
  Mul a b -> eval a * eval b
  Div a b -> eval a / eval b

--возвращает список возможных операций для двух чисел. Для 4, 5 вернет [Plus 4 5..Div 4 5]
operations a b = if eval b == 0 then safeOps else Div a b:safeOps --нужно проверять деление на 0, в таком случае не возвращать Div a b
                                             where safeOps = [Plus a b, Minus a b, Mul a b]
--превращает строку в число типа Exp Rational
parseRational = Number . toRational . read

--список возможных выражений для числа, представленного в виде строки
permutations :: String -> [Exp Rational]
permutations [] = []
permutations [x] = [parseRational [x]]
permutations xs = do --здесь рассматриваем список как монаду для удобства
  (y:ys) <- map (map parseRational) $ combinations xs -- возможные комбинации разделений вида [["1, "2"], ["12"]]
  foldM operations y ys --operations - монадическая функция вида a -> m b для монады списков, соответственно применяем монадическую свертку, как бы "сшивая" полученные комбинации разделений всевозможными арифметическими операциями
    where
      combinations :: [a] -> [[[a]]]
      combinations [] = []
      combinations [x] = [[[x]]]
      combinations (x:xs) = map (\(y:ys) -> (x:y):ys) (combinations xs)  ++ map ([x]:) (combinations xs)
main = do
  number <- getLine
  print $  filter ((== 100) . eval) $ permutations number --фильтруем среди всех возможных выражений те, которые дают 100