import scala.io.StdIn.{readInt,readLine}

object Main {

  def printStable(l:Array[(Char,Int)],a:Array[(Char,Int)]) = {
    val s = l.groupBy(_._2).filter(_._2.length > 1)
    var stable = true

    for {
      i <- s
      if stable
    }
      if(a.filter(_._2 == i._1).toSeq != i._2.toSeq)
        stable = false

    if(stable)
      println("Stable")
    else
      println("Not stable")
  }

  def swap(a:Array[(Char,Int)],x:Int,y:Int) = {
    val t = a(x)
    a(x) = a(y)
    a(y) = t
  }

  def bubbleSort(a:Array[(Char,Int)]) =
    for(i <- 0 until a.length)
      for(j <- a.length-1 to i+1 by -1)
        if(a(j)._2 < a(j-1)._2)
          swap(a,j,j-1)

  def selectionSort(a:Array[(Char,Int)]) =
    for(i <- 0 until a.length) {
      var mini = i
      for(j <- i until a.length)
        if(a(j)._2 < a(mini)._2) mini = j
      swap(a,i,mini)
    }

  def main(args:Array[String]) = {
    val n = readInt
    val l = readLine.split(" ").map(s => (s(0),s.drop(1).toInt))
    val a = l.clone
    val b = a.clone
    bubbleSort(a)
    selectionSort(b)

    println(a.map((x)=>x._1.toString+x._2).mkString(" "))
    printStable(l,a)
    println(b.map((x)=>x._1.toString+x._2).mkString(" "))
    printStable(l,b)
  }
}