module Main where

import Data.Bool
import Data.Functor
import Data.List
import Data.Ord

main :: IO ()
main = do
  { [n] <- getInts
  ; cs <- getCards
  ; let ds = bubbleSortBy (comparing (!!1)) cs
  ; let es = selectionSortBy (comparing (!!1)) cs
  ; putCards ds
  ; putStrLn "Stable"
  ; putCards es
  ; putStrLn $ bool "Not stable" "Stable" (ds == es)
  }

bubbleSortBy :: (a -> a -> Ordering) -> [a] -> [a]
bubbleSortBy cmp = step []
  where
    step xs [] = xs
    step xs ys = case bubbleBy cmp ys of
      (z,zs) -> step (z:xs) zs

bubbleBy :: (a -> a -> Ordering) -> [a] -> (a, [a])
bubbleBy cmp (x:xs) = mapAccumL (swapBy cmp) x xs

swapBy :: (a -> a -> Ordering) -> a -> a -> (a, a)
swapBy cmp x y = case x `cmp` y of
  GT -> (x,y)
  _  -> (y,x)

selectionSortBy :: Eq a => (a -> a -> Ordering) -> [a] -> [a]
selectionSortBy cmp xs = unfoldr phi xs
  where
    phi [] = Nothing
    phi xxs@(x : xs) = case break (minx ==) xxs of
      ([], _) -> Just (x, xs)
      (y : ys, z : zs) -> Just (z, ys ++ y : zs)
      where
        minx = minimumBy cmp xxs
        
type Card = [Char]

getCards :: IO [Card]
getCards = words <$> getLine

putCards :: [Card] -> IO ()
putCards = putStrLn . unwords

getInts :: IO [Int]
getInts = map read . words <$> getLine