import Data.List
import Data.Char

type Card = (Char, Int)

bubbleSort :: [Card] -> [Card]
bubbleSort xs = loop (1, xs)
  where
    loop (0, xs) = xs
    loop (1, xs) = loop $ foldr f (0, xs) [0 .. length xs - 2]
    f i (flag, xs)
      | (snd b) > (snd c) = (1, as ++ c : b : ds)
      | otherwise         = (flag, xs)
      where (as, b : c : ds) = splitAt i xs

findMinimumIndex :: [Card] -> Int
findMinimumIndex (x : xs) = (\(minj, _, _) -> minj) $ foldl f (0, 1, x) xs
  where f (minj, i, v) x = if (snd x) < (snd v) then (i, i + 1, x) else (minj, i + 1, v)

swapMinimum :: [Card] -> Int -> [Card]
swapMinimum xs i = if i > 0 then b : as ++ a : bs else xs
  where (a : as, b : bs) = splitAt i xs

selectionSort :: [Card] -> [Card]
selectionSort xs = foldl f xs [0 .. length xs - 2]
  where
    f xs i = as ++ ys
      where
        (as, bs) = splitAt i xs
        ys = swapMinimum bs $ findMinimumIndex bs

test :: [Card] -> [Card]
test xs = sortBy (\a b -> compare (snd a) (snd b)) xs

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

