import java.util.Scanner
import scala.collection.mutable

class Card(s: String, n: Int) {
  val suit: String = s
  val num: Int = n
  override def toString = suit + num
  override def equals(other: Any) = other match {
    case that: Card => this.suit == that.suit && this.num == that.num
    case _ => false
  }
}

object Card {
  def apply(text: String): Card = new Card(text take 1, (text drop 1).toInt)
}


object Main extends App {

  val sc = new Scanner(System.in)

  def next() = sc.next
  def nextInt() = next.toInt

  def bubbleSort(x: mutable.Seq[Card]): Seq[Card] = {
    val n = x.length
    for {
      i <- 0 to n-1
	  j <- n-1 to i+1 by -1
    } if(x(j).num < x(j-1).num) {
        val tmp = x(j)
        x(j) = x(j-1)
        x(j-1) = tmp
    }
    x
  }

  def selectionSort(x: mutable.Seq[Card]): Seq[Card] = {
    val n = x.length
    for (i <- 0 until n) {
      val minj = (i /: (i until n)) { (minj, j) =>
        if (x(j).num < x(minj).num) j
        else minj
      }
      val tmp = x(i)
      x(i) = x(minj)
      x(minj) = tmp
    }
    x
  }

  def testStability(xs: Seq[Card], ys: Seq[Card]): Boolean = {
    def loop(ns: List[Int]): Boolean = ns match {
      case n :: ns =>
        if (xs.filter(_.num == n) == ys.filter(_.num == n)) loop(ns)
        else false
      case Nil => true
    }
    loop((1 to 9).toList)
  }


  val n = nextInt
  val cards = mutable.Seq.fill(n)(Card(next))

  val bubble = bubbleSort(cards.clone)
  println(bubble mkString " ")
  println(if (testStability(cards, bubble)) "Stable" else "Not stable")

  val selection = selectionSort(cards.clone)
  println(selection mkString " ")
  println(if (testStability(cards, selection)) "Stable" else "Not stable")
}

