import Data.Char
import Control.Applicative

type Card = (Char, Int)

cardFromString :: String -> Card
cardFromString [m, v] = (m, digitToInt v)

cardToString :: Card -> String
cardToString (m, v) = [m, intToDigit v]

cardMark :: Card -> Char
cardMark (m, _) = m

cardNum :: Card -> Int
cardNum (_, v) = v

bubbleSort :: [Card] -> [Card]
bubbleSort [card] = [card]
bubbleSort cards =
    card1:(bubbleSort cards1)
    where
        (card1:cards1) = bubbling cards

bubbling :: [Card] -> [Card]
bubbling [card] = [card]
bubbling (card:cards) =
    if cardNum card <= cardNum card1
        then (card:card1:cards1)
        else (card1:card:cards1)
    where
        (card1:cards1) = bubbling cards

minCard :: [Card] -> Card
minCard (c:cs) =
    loop c cs
    where
        loop :: Card -> [Card] -> Card
        loop c [] = c
        loop c1 (c2:cs)
          | cardNum c1 <= cardNum c2 = loop c1 cs
          | otherwise                = loop c2 cs

select :: [Card] -> [Card]
select (card:cards) =
    if card == mcard
       then mcard:cards
       else mcard:(replace mcard card cards)
    where
        mcard = minCard (card:cards)
        replace :: Card -> Card -> [Card] -> [Card]
        replace _ _ [] = []
        replace old new (c:cs)
          | old == c  = new:cs
          | otherwise = c:(replace old new cs)

selectionSort :: [Card] -> [Card]
selectionSort [card]       = [card]
selectionSort cards =
    card1:(selectionSort cards1)
    where
        (card1:cards1) = select cards

marks :: Int -> [Card] -> [Char]
marks n = map cardMark . filter (\c -> cardNum c == n)

isStable :: [Card] -> [Card] -> Bool
isStable cards orders =
    loop (map cardNum cards) cards orders
    where
        loop :: [Int] -> [Card] -> [Card] -> Bool
        loop [] _ _ = True
        loop (n:ns) cards orders
          | marks n cards == marks n orders = loop (remove n ns) cards orders
          | otherwise = False
        remove :: Int -> [Int] -> [Int]
        remove n = filter (/=n)

printResult :: [Card] -> [Card] -> IO ()
printResult cards orders = do
    putStrLn $ unwords (cardToString <$> orders)
    if isStable cards orders
       then putStrLn "Stable"
       else putStrLn "Not stable"

main :: IO ()
main = do
    getLine
    cards <- map cardFromString . words <$> getLine :: IO [Card]
    printResult cards (bubbleSort cards)
    printResult cards (selectionSort cards)

