import scala.io.StdIn._

object Main extends App {

  def isLeftSmall(c1: String, c2: String): Boolean = {
    if (c1.takeRight(1).toInt < c2.takeRight(1).toInt) true else false
  }
  
  def bubbleSort(c: Array[String], n: Int) {
    for(i <- (0 to n - 1)) {
      for (j <- (n - 1 until i by -1)) {
        if (isLeftSmall(c(j), c(j - 1))) {
          val tmp_v = c(j)
          c(j) = c(j - 1)
          c(j - 1) = tmp_v
        }
      }
    }
    println(c.mkString(" "))
    println("Stable")
  }

  def selectionSort(c: Array[String], n: Int) {
    for (i <- (0 to n - 1)) {
      var min_j = i
      for (j <- (i to n - 1)) {
        if (isLeftSmall(c(j), c(min_j))) {
          min_j = j
        }
      }
      val tmp_v = c(i)
      c(i) = c(min_j)
      c(min_j) = tmp_v
    }
    println(c.mkString(" "))
  }
  
  val n = readLine.toInt
  val c = readLine.split(" ").toArray
  val c1 = c.clone
  val c2 = c.clone
  bubbleSort(c1, n)
  selectionSort(c2, n)
  if (c1 sameElements c2) println("Stable") else println("Not stable")
}
