import Data.List
import Control.Applicative
import Control.Monad
import Data.Monoid
import qualified Data.Foldable as F

data Card = Card { suit :: Char, num :: Int } deriving (Eq)

instance Show Card where
    show (Card suit num) = suit:show num

newtype CardNum = CardNum { getCard :: Card } deriving (Show)

instance Eq CardNum where
    CardNum (Card _ x) == CardNum (Card _ y) = x == y

instance Ord CardNum where
    CardNum (Card _ x) `compare` CardNum (Card _ y) = x `compare` y

myread :: String -> Card
myread (x:xs) = Card x (read xs)


main :: IO ()
main = do
    getLine
    input <- map myread . words <$> getContents
    let bsorted = bubbleSort $ map CardNum input
        ssorted = selectionSort $ map CardNum input
    putStrLn $ intercalate " " $ map (show . getCard) bsorted
    putStrLn $ if isStable input bsorted then "Stable" else "Not stable"
    putStrLn $ intercalate " " $ map (show . getCard) ssorted
    putStrLn $ if isStable input ssorted then "Stable" else "Not stable"


bubbleSort :: (Ord a) => [a] -> [a]
bubbleSort [] = []
bubbleSort xs = let (m, others) = minOthers xs
                in m:bubbleSort others
    where changeOrThrough x (y, ys)
              | x <= y    = (x, y:ys)
              | otherwise = (y, x:ys)
          minOthers xs = foldr changeOrThrough (last xs, []) (init xs)

selectionSort :: (Ord a) => [a] -> [a]
selectionSort [] = []
selectionSort all@(x:_) = let m = minimum all
                          in m:(selectionSort . tail $ firstReplace m x all)
    where firstReplace a b (x:xs)
              | x == a    = b:xs
              | otherwise = x:firstReplace a b xs

isStable :: [Card] -> [CardNum] -> Bool
isStable xs ys = getAll $ F.foldMap (\ys' -> All $ isPartStable xs ys') (group ys)
    where isPartStable xs ys' = map getCard ys' == filter (\x -> num x == (num . getCard $ head ys')) xs

