object Main extends App {
  import java.{ util => ju }
  import scala.annotation._
  import scala.collection._
  import scala.collection.{ mutable => mu }
  import scala.collection.JavaConverters._
  import scala.math._
  import scala.io.StdIn.readLine

  val sc = new ju.Scanner(System.in)

  val n = sc.nextInt()
  var array = Array.fill[String](n)(sc.next())
  val bubble = bubbleSort(array)
  val selection = selectionSort(array)
  printArray(bubble)
  println("Stable")
  printArray(selection)
  println(if (compareArray(bubble, selection)) "Stable" else "Not Stable")

  def bubbleSort(nums: Array[String]): Array[String] = {
    var result = nums.clone()
    val n = result.length
    for (i <- 0 until n) {
      for (j <- n - 1 until i by -1) {
        if (compareString(result(j), result(j - 1))) {
          val bigger = result(j)
          result(j) = result(j - 1)
          result(j - 1) = bigger
        }
      }
    }
    result
  }

  def selectionSort(nums: Array[String]): Array[String] = {
    var result = nums.clone()
    for (i <- 0 until n) {
      var min = i
      for (j <- i to n - 1) {
        if (compareString(result(j), result(min))) {
          min = j
        }
      }
      if (min != i) {
        val bigger = result(min)
        result(min) = result(i)
        result(i) = bigger
      }
    }
    result
  }

  def compareString(s1: String, s2: String): Boolean = {
    s1.charAt(1) < s2.charAt(1)
  }

  def printArray(nums: Array[String]) {
    for (i <- 0 until nums.length - 1) print(nums(i) + " ")
    println(nums.last)
  }

  def compareArray(bubble: Array[String], selection: Array[String]): Boolean = {
    for (i <- 0 until bubble.length) {
      if (!bubble(i).equals(selection(i))) return false
    }
    true
  }
}