import scala.io.StdIn.{readInt, readLine}
object Main {
    def main(args: Array[String]): Unit = {
        val len = readInt
        val arr = readLine.split(" ").map(a => (a, a.substring(1).toInt))
        val retBubble = bubbleSort(arr, len).map(_._1).mkString(" ")
        val retSelection = selectionSort(arr, len).map(_._1).mkString(" ")
        println(retBubble)
        println("Stable")
        println(retSelection)
        println(if (retBubble == retSelection) "Stable" else "Not stable")
    }
    
    def swap(arr: Array[(String, Int)], a: Int, b: Int): Unit = {
        val tmp = arr(a)
        arr(a) = arr(b)
        arr(b) = tmp
    }
    
    def bubbleSort(arr: Array[(String, Int)], len: Int): Array[(String, Int)] = {
        val copy = new Array[(String, Int)](len)
        arr.copyToArray(copy)
        (1 until len).foreach { i =>
            (i until len).reverse.foreach { j =>
                if (copy(j)._2 < copy(j - 1)._2) swap(copy, j, j - 1)
            }
        }
        copy
    }
    
    def selectionSort(arr: Array[(String, Int)], len: Int): Array[(String, Int)] = {
        val copy = new Array[(String, Int)](len)
        arr.copyToArray(copy)
        def min(arr: Array[(String, Int)], ptr: Int): Int = {
            if ((arr.length - 1 == ptr)) ptr
            else min(arr, ptr + 1) match {
                case m if arr(m)._2 < arr(ptr)._2 => m
                case _ => ptr
            }
        }
        (0 until len).foreach { i => 
            val m = min(copy, i)
            if (i != m) swap(copy, i, m)
        }
        copy
    }
}
