{-# LANGUAGE ScopedTypeVariables #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.ST
import           Data.Array.MArray
import           Data.Array.ST
import           Data.STRef

newtype Card =
    Card String
    deriving Eq

instance Ord Card where
    compare (Card [a, b]) (Card [c, d]) = compare b d

instance Show Card where
    show (Card cs) = cs

show' :: Show a => [a] -> String
show' = unwords . fmap show

bubble :: forall a. Ord a => [a] -> [a]
bubble xs =
    runST $ do
        let n = length xs
        a <- newListArray (0, n - 1) xs :: ST s (STArray s Int a)
        forM_ [0 .. n - 1] $ \i -> do
            forM_ [n - 1,n - 2 .. i + 1] $ \j -> do
                e1 <- readArray a j
                e2 <- readArray a (j - 1)
                when (e1 < e2) $ do
                    writeArray a (j - 1) e1
                    writeArray a j e2
        getElems a

selection :: forall a. Ord a => [a] -> [a]
selection xs =
    runST $ do
        let n = length xs
        minjRef <- newSTRef 0
        a <- newListArray (0, n - 1) xs :: ST s (STArray s Int a)
        forM_ [0 .. n - 1] $ \i -> do
            writeSTRef minjRef i
            forM_ [i .. n - 1] $ \j -> do
                minj <- readSTRef minjRef
                e1 <- readArray a j
                e2 <- readArray a minj
                when (e1 < e2) $ do
                    writeSTRef minjRef j
            minj <- readSTRef minjRef
            e1 <- readArray a i
            e2 <- readArray a minj
            writeArray a minj e1
            writeArray a i e2
        getElems a

main :: IO ()
main = do
    getLine
    xs <- fmap Card . words <$> getLine :: IO [Card]
    let b = show' $ bubble xs
    let s = show' $ selection xs
    putStrLn b
    putStrLn "Stable"
    putStrLn s
    if b == s
       then putStrLn "Stable"
       else putStrLn "Not stable"

