fun bubbleSort(cards: List<String>, n: Int) : List<String> {
  var c = cards.toMutableList()
  for (i in (0 until n)) {
    for (j in (n-1 downTo i+1)) {
      val x = Integer.valueOf(c[j][1].toString())
      val y = Integer.valueOf(c[j-1][1].toString())
      if (x < y) {
        val tmp = c[j]
        c[j] = c[j-1]
        c[j-1] = tmp
      }
    }
  }
  return c
}

fun selectionSort(cards: List<String>, n: Int) : List<String> {
  var c = cards.toMutableList()
  (0 until n).forEach { i ->
    var minX = i
    (i until n).forEach { j ->
      val a = Integer.valueOf(c[j][1].toString())
      val b = Integer.valueOf(c[minX][1].toString())
      if (a < b) {
        minX = j
      }
    }
    val a = Integer.valueOf(c[i][1].toString())
    val b = Integer.valueOf(c[minX][1].toString())
    if (a != b) {
      val tmp = c[i]
      c[i] = c[minX]
      c[minX] = tmp
    }
  }
  return c
}

fun isStable(inArr: List<String>, outArr: List<String>, n: Int): Boolean {
  for (i in (0 until n)) {
    for (j in (i+1 until n)) {
      for (a in (0 until n)) {
        for (b in (a+1 until n)) {
          if (inArr[i][1] == inArr[j][1] && inArr[i] == outArr[b] && inArr[j] == outArr[a]) {
            return false
          }
        }
      }
    }
  }
  return true
}

fun main(args: Array<String>) {
  val n = readLine()!!.toInt()
  val cards = readLine()!!.split(" ")

  val bubbleSortedCards = bubbleSort(cards, n)
  val selectionSortedCards = selectionSort(cards, n)
  println(bubbleSortedCards.joinToString(" "))
  println(if (isStable(cards, bubbleSortedCards, n)) "Stable" else "Not stable")
  println(selectionSortedCards.joinToString(" "))
  println(if (isStable(cards, selectionSortedCards, n)) "Stable" else "Not stable")
}
