import qualified Data.Vector         as V
import qualified Data.Vector.Mutable as VM
import Control.Applicative
import Control.Monad
import Data.IORef
import Data.Char
import Data.List

-- 1 BubbleSort(C, N)
-- 2   for i = 0 to N-1
-- 3     for j = N-1 downto i+1
-- 4       if C[j].value < C[j-1].value
-- 5         C[j] と C[j-1] を交換
-- 6
-- 7 SelectionSort(C, N)
-- 8   for i = 0 to N-1
-- 9     minj = i
-- 10    for j = i to N-1
-- 11      if C[j].value < C[minj].value
-- 12        minj = j
-- 13    C[i] と C[minj] を交換

bubbleSort :: [(Char, Int)] -> IO [(Char, Int)]
bubbleSort xs = do
  aVec <- V.thaw $ V.fromList xs
  let len = length xs - 1
  forM_ [0 .. len] $ \i -> do
    forM_ [len, len - 1 .. (i + 1)] $ \j -> do
      (_, v1) <- VM.read aVec j
      (_, v2) <- VM.read aVec (j - 1)
      when (v1 < v2) $ VM.swap aVec j (j - 1)
  V.toList <$> V.freeze aVec

selectionSort :: [(Char, Int)] -> IO [(Char, Int)]
selectionSort xs = do
  aVec <- V.thaw $ V.fromList xs
  let len = length xs - 1
  forM_ [0 .. len] $ \i -> do
    minj <- newIORef i
    forM_ [i .. len] $ \j -> do
      (_, v1) <- VM.read aVec j
      k  <- readIORef minj
      (_, v2) <- VM.read aVec k
      when (v1 < v2) $ writeIORef minj j
    k <- readIORef minj
    VM.swap aVec i k
  V.toList <$> V.freeze aVec

test :: [(Char, Int)] -> [(Char, Int)]
test xs = sortBy (\ (_, a) (_, b) -> compare a b) xs

main :: IO ()
main = do
  _  <- getLine
  xs <- map (\[a, b] -> (a, digitToInt b)) . words <$> getLine
  let tl = test xs
  bl <- bubbleSort xs
  display bl tl
  sl <- selectionSort xs
  display sl tl
    where
      display xs ys = do
        putStrLn $ unwords $ map (\(a, b) -> (a : show b)) xs
        putStrLn $ if xs == ys
          then "Stable"
          else "Not stable"

