import java.io.BufferedReader
import java.io.InputStreamReader

data class Card(val suit: Char, val value: Char) {
    override fun toString(): String {
        return "$suit$value"
    }
}

fun bubbleSort(a: Array<Card>) {
    for (i in 0 until a.size) {
        for (j in a.size-1 downTo i+1) {
            if (a[j].value < a[j-1].value) {
                run { val t = a[j]; a[j] = a[j-1]; a[j-1] = t }
            }
        }
    }
}

fun selectionSort(a: Array<Card>) {
    for (i in 0 until a.size) {
        val minIdx = (i until a.size).minBy { a[it].value }
        minIdx?.let { val t = a[i]; a[i] = a[minIdx]; a[minIdx] = t }
    }
}

fun isStable(a: Array<Card>, b: Array<Card>) =
        (0 until a.size).all { it -> a[it].suit == b[it].suit }

fun main(args: Array<String>) {
    val a = BufferedReader(InputStreamReader(System.`in`))
            .readText()
            .trim()
            .split(regex = """\s+""".toRegex())
            .drop(n = 1)
            .map { Card(it[0], it[1]) }
            .toTypedArray()


    val b = a.copyOf()

    bubbleSort(a)
    selectionSort(b)

    println(a.joinToString(" "))
    println("Stable")
    println(b.joinToString(" "))
    println(if (isStable(a, b)) "Stable" else "Not stable")
}
