import java.util.Scanner

import scala.collection.mutable.ArrayBuffer

object Main {

  import ExtendedString._

  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val n = sc.nextInt()
    val cards = Vector.fill(n)(sc.next())

    val bubCared = bub(n, ArrayBuffer.apply(cards: _*))
    val selCared = sel(n, ArrayBuffer.apply(cards: _*))
    println(bubCared.mkString(" "))
    println(isStable(cards, bubCared.toVector))
    println(selCared.mkString(" "))
    println(isStable(cards, selCared.toVector))
  }

  def bub(n: Int, cards: ArrayBuffer[String]): ArrayBuffer[String] = {
    (0 to n - 1).foreach { i =>
      (n - 1 to(i + 1, -1)).foreach { j =>
        if (cards(j).getCardValue < cards(j - 1).getCardValue) {
          val cj = cards(j)
          val cjMinusOne = cards(j - 1)
          cards(j) = cjMinusOne
          cards(j - 1) = cj
        }
      }
    }
    cards
  }

  def sel(n: Int, cards: ArrayBuffer[String]): ArrayBuffer[String] = {
    (0 to n - 1).foreach { i =>
      var minj = i
      (i to n - 1).foreach { j =>
        if (cards(j).getCardValue < cards(minj).getCardValue) {
          minj = j
        }
      }
      val ci = cards(i)
      val cmin = cards(minj)
      cards(i) = cmin
      cards(minj) = ci
    }
    cards
  }

  def isStable(before: Vector[String], after: Vector[String]): String = {
    val afterGroup = after.groupBy(_.getCardValue)
    before.groupBy(_.getCardValue).forall { case (i, b) =>
      afterGroup(i) == b
    } match {
      case true => "Stable"
      case false => "Not stable"
    }
  }

}

object ExtendedString {

  implicit class CardString(str: String) {
    def getCardValue = str.last.toInt
  }

}
