module Main where
-- import Debug.Trace
import Data.List
import Data.Char
import Data.Array
import Data.Maybe
import Data.Ord
import Control.Monad

data Suit = Spade | Hart | Club | Diamond deriving (Eq)
data Card = Card Suit Int deriving (Eq)
instance Ord Card where
    compare (Card _ a) (Card _ b) = compare a b
instance Show Card where
    show (Card Spade   i) = "S"++show i
    show (Card Hart    i) = "H"++show i
    show (Card Club    i) = "C"++show i
    show (Card Diamond i) = "D"++show i

solve :: Int -> [Card] -> [([Card], String)]
solve n l = [(bl, stable ol bl), (sl, stable ol sl)] where
    bl = bSort l
    sl = sSort n l
    ol = sort l
    stable ol cl = if ol == cl then "Stable" else "Not stable" 

bSort :: [Card] -> [Card]
bSort l = iter 0 [] l where
    iter c sl [] = sl
    iter c sl l = iter2 c [] l where
        iter2 c ac [x] = iter c (x:sl) (reverse ac)
        iter2 c ac (x:y:ds)
            | x <= y     = iter2 (c) (x:ac) (y:ds)
            | otherwise = iter2 (c+1) (y:ac) (x:ds)

sSort :: Int -> [Card] -> [Card]
sSort n l = iter 0 (0, listArray (0, n-1) l) where
    iter p (c, ar)
        | p >= n    = elems ar
        | otherwise = iter (p+1) (setMin p p) where
            setMin i mi
                | i < n     = setMin (i+1) $ if ar!i < ar!mi then i else mi
                | mi == p   = (c, ar) 
                | otherwise = (c+1, ar // [(p, ar!mi), (mi, ar!p)])

toStr :: [Card] -> String
toStr l = init (concatMap (\x-> show x ++ " ") l)

readLine:: IO [Card]
readLine = fmap (map readCards . words) getLine where
    readCards c = case c of
        ('S':s) -> Card Spade   (read s)
        ('H':s) -> Card Hart    (read s)
        ('C':s) -> Card Club    (read s)
        ('D':s) -> Card Diamond (read s)

main :: IO() 
main = do
    n <- readLn :: IO Int
    l <- readLine
    mapM_ putStrLn $ concatMap (\(rl,s) -> [toStr rl, s]) (solve n l)

