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

    val bubbleSorted = bubbleSort(cards)
    val selectionSorted = selectionSort(cards)

    println(bubbleSorted.joinToString(" "))
    println("Stable")
    println(selectionSorted.joinToString(" "))

    (0 until n).all {
        bubbleSorted[it] == selectionSorted[it]
    }.run {
        println(if (this) "Stable" else "Not stable")
    }
}

private fun bubbleSort(cards: List<String>): List<String> {
    val n = cards.size
    val xs = cards.toMutableList()

    for (i in 0 until n) {
        for (j in n - 1 downTo i + 1) {
            val v1 = xs[j][1].toInt()
            val v2 = xs[j - 1][1].toInt()
            if (v1 < v2) {
                val t = xs[j]
                xs[j] = xs[j - 1]
                xs[j- 1] = t
            }
        }
    }

    return xs
}

private fun selectionSort(cards: List<String>): List<String> {
    val n = cards.size
    val xs = cards.toMutableList()

    for (i in 0 until n) {
        var mini = i
        for (j in i until n) {
            val v1 = xs[j][1].toInt()
            val v2 = xs[mini][1].toInt()
            if (v1 < v2) {
                mini = j
            }
        }
        if (mini > i) {
            val t = xs[i]
            xs[i] = xs[mini]
            xs[mini] = t
        }
    }

    return xs
}
