data WeightCharacterTuple = WeightCharacterTuple {

        weight :: Int,

        character :: Char

}deriving (Show)

instance Eq WeightCharacterTuple where

        (WeightCharacterTuple a _) == (WeightCharacterTuple b _) = a==b

instance Ord WeightCharacterTuple where

        (WeightCharacterTuple a _) > (WeightCharacterTuple b _) = a > b

        (WeightCharacterTuple a _) >= (WeightCharacterTuple b _) = a >= b

        (WeightCharacterTuple a _) < (WeightCharacterTuple b _) = a <>

        (WeightCharacterTuple a _) <= (WeightCharacterTuple b _) = a <= b

data Tree a = Node a (Tree a) (Tree a) | Leaf a

        deriving (Show)

instance Eq a => Eq (Tree a) where

        (==) (Node node1 _ _)   (Node node2 _ _)        = node1 == node2

        (==) (Node node1 _ _)   (Leaf node2)            = node1 == node2

        (==) (Leaf node1)       (Node node2 _ _)        = node1 == node2

        (==) (Leaf node1)       (Leaf node2)            = node1 == node2

operateOnTwoTreeNodes operation left right =

        operation l r

                where

                        l=nodeFromTree left

                        r=nodeFromTree right

                        nodeFromTree tree = case tree of

                                                (Node n _ _) -> n

                                                (Leaf n) -> n

instance Ord a => Ord (Tree a) where

        left >= right =  operateOnTwoTreeNodes (>=) left right

        left < right ="  operateOnTwoTreeNodes">

repeats :: String -> [WeightCharacterTuple]

repeats string = quickSort $ zipWith WeightCharacterTuple counts uniqueLetters

        where

        counts = map (frequency string) uniqueLetters

        frequency :: String -> Char -> Int

        frequency (x:xs) c

                | c == x        = 1 + frequency xs c

                | otherwise     = frequency xs c

        frequency _ c   = 0

        uniqueLetters = unique string

unique :: String -> String -- get the unique letters in the string

unique (x:xs)   = [x] ++ unique [y | y <- xs, y /= x ]

unique []               = []

huffman :: [Tree WeightCharacterTuple] -> [Tree WeightCharacterTuple]

huffman (min1:min2:rest) = huffman newList

        where

        newList

                | length rest /= 0 =  quickSort ((merge min1 min2):rest) -- TODO Sorting of the list is required

                | otherwise = [merge min1 min2]

        merge (Node node left right) (Leaf leaf)

                | node <= leaf = Node (WeightCharacterTuple newWeight '*') (Node node left right) (Leaf leaf)

                | otherwise    = Node (WeightCharacterTuple newWeight '*') (Leaf leaf) (Node node left right)

                where

                newWeight = (weight leaf) + (weight node)

        merge (Leaf leaf) (Node node left right)

                | node <= leaf = Node (WeightCharacterTuple newWeight '*') (Node node left right) (Leaf leaf)

                | otherwise    = Node (WeightCharacterTuple newWeight '*') (Leaf leaf) (Node node left right)

                where

                newWeight = (weight leaf) + (weight node)

        merge (Leaf leaf1) (Leaf leaf2)

                | leaf1 <= leaf2 = Node (WeightCharacterTuple newWeight '*') (Leaf leaf1) (Leaf leaf2)

                | otherwise =      Node (WeightCharacterTuple newWeight '*') (Leaf leaf2) (Leaf leaf1)

                where

                newWeight = (weight leaf1) + (weight leaf2)

huffman x = x

quickSort (x:xs) = l1 ++ [x] ++ l2 -- items less than x + x + items bigger than x

        where

                l1 = quickSort [y | y <- xs, y <>

                l2 = quickSort [y | y <- xs, y >= x] -- sorted items greater than x

quickSort [] = []

main=do

        x <- getLine

        let y1=unique x

        let y2=repeats x

        putStrLn (show y1)

        putStrLn (show y2)

        let y=map Leaf y2

        let z = huffman y

        putStrLn (show z)

        return ()