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

object Main extends App {

  case class Card(suit: Char, num: Int)

  val N = readInt
  val cards = readLine.split(" ").map(e => Card(e.charAt(0), e.charAt(1).asDigit))
  val cards1 = cards.clone()
  val cards2 = cards.clone()

  val bubbleSorted = bubbleSort(cards1, N)
  val selectionSorted = selectionSort(cards2, N)

  println(bubbleSorted.map(e => e.suit.toString + e.num).mkString(" "))
  println("Stable")

  println(selectionSorted.map(e => e.suit.toString + e.num).mkString(" "))
  println(if (isStable(bubbleSorted, selectionSorted, N)) "Stable" else "Not stable")


  def swap(arr: Array[Card], n: Int, m: Int): Unit = {
    val tmp = arr(n)
    arr(n) = arr(m)
    arr(m) = tmp
  }

  def isStable(arr1: Array[Card], arr2: Array[Card], n: Int): Boolean = {
    (0 until n).foreach {
      i => if (arr1(i).suit != arr2(i).suit) return false
    }
    true
  }

  def bubbleSort(arr: Array[Card], n: Int): Array[Card] = {
    (0 until n).foreach { i =>
      (n - 1 until i by -1).foreach { j =>
        if (arr(j).num < arr(j - 1).num) {
          swap(arr, j, j - 1)
        }
      }
    }
    arr
  }

  def selectionSort(arr: Array[Card], n: Int): Array[Card] = {
    (0 until n).foreach { i =>
      var minj = i
      (i until n).foreach { j =>
        minj = if (arr(j).num < arr(minj).num) j else minj
      }
      swap(arr, minj, i)
    }
    arr
  }
}

