import Data.Functor( (<$>))
import Data.Array.IArray
import Data.Array.MArray
import Data.Array.IO
import Control.Monad

main = do
    n <- read <$> getLine
    cards <- words <$> getLine
    let
	bubbleSort []	= []
	bubbleSort list = r:bubbleSort esult
	  where
	    r:esult = bubbleScan (reverse list) []

	    bubbleScan [x] l		= x:l
	    bubbleScan (x1:x2:xs) l
		|  x1!!1 < x2!!1	= bubbleScan (x1:xs) (x2:l) 
		| otherwise		= bubbleScan (x2:xs) (x1:l)

	bsorted = bubbleSort cards

    putStrLn $ unwords bsorted
    putStrLn "Stable"
    a <- newListArray (0,n-1) cards		::IO (IOArray Int String)
    let
	selectionScan i_
	  = do
	    let
		searchMinIx::String -> Int -> Int -> IO Int
		searchMinIx nowMin ixNowMin iterator
		  | n <= iterator		    = return ixNowMin
		  | otherwise
		    = do
			v <- readArray a iterator
			if v!!1 < nowMin!!1
			then searchMinIx    v	iterator (iterator+1)
			else searchMinIx nowMin ixNowMin (iterator+1)

		swap::Int -> Int -> IO ()
		swap i j = do
		    temp <- readArray a i
		    writeArray a i =<< readArray a j
		    writeArray a j temp

	    startmin <- readArray a i_
	    ixmin <- searchMinIx startmin i_ i_
	    swap i_ ixmin
    
    forM_ [0..n-1] selectionScan
    ia <- freeze a  ::IO (Array Int String)
    let
	ssorted = elems ia

    putStrLn $ unwords ssorted
    putStrLn $ if ssorted == bsorted
		then "Stable"
		else "Not stable"

