object Main {
  def main(args: Array[String]): Unit = {
    val scanner = new java.util.Scanner(System.in)

    val a = Array.fill(scanner.nextInt)(parse(scanner.next))
    val b = bubbleSort(a)
    val s = SelectionSort(a)
    println(b.map(t => s"${t._1}${t._2}").mkString(" "))
    println(if(checkStable(b, a)) "Stable" else "Not stable")
    println(s.map(t => s"${t._1}${t._2}").mkString(" "))
    println(if(checkStable(s, a)) "Stable" else "Not stable")
  }

  def checkStable(target: Seq[(Char, Int)], original: Seq[(Char, Int)]): Boolean =
    (1 to 9).find(i => !target.filter(_._2 == i).equals(original.filter(_._2 == i))).isEmpty

  def parse(card: String): (Char, Int) =
    (card(0), card.substring(1).toInt)

  def bubbleSort(a: Seq[(Char, Int)]): Seq[(Char, Int)] = {
    val c = new Array[(Char, Int)](a.length)
    a.copyToArray(c)
    for(i <- 0 until c.length) {
      for(j <- c.length - 1 to i + 1 by -1) {
        if(c(j)._2 < c(j - 1)._2) {
          val t = c(j)
          c(j) = c(j - 1)
          c(j - 1) = t
        }
      }
    }
    c
  }

  def SelectionSort(a: Seq[(Char, Int)]): Seq[(Char, Int)] = {
    val c = new Array[(Char, Int)](a.length)
    a.copyToArray(c)
    var minj = 0
    for(i <- 0 until c.length) {
      minj = i
      for(j <- i until c.length) {
        if(c(j)._2 < c(minj)._2) {
          minj = j
        }
      }
      val t = c(i)
      c(i) = c(minj)
      c(minj) = t
    }
    c
  }
}

