fun main(args: Array<String>) {
    fun MutableList<String>.num(index: Int): Int {
        return this[index].substring(1, this[index].length).toInt()
    }

    fun checkStable(i1: Int, i2: Int): Boolean {
        return i1 == i2
    }

    val n = readLine()!!.toInt()
    val c = readLine()!!.split(" ").toMutableList()
    var cStable = true
    val c2 = c.toMutableList()
    var c2Stable = true

    for (i in 0 until n) {
        for (j in n - 1 downTo i + 1) {
            if (c.num(j) < c.num(j - 1)) {
                val temp = c[j - 1]
                c[j - 1] = c[j]
                c[j] = temp
                if (checkStable(c.num(j - 1), c.num(j))) {
                    cStable = false
                }
            }
        }
    }

    for (i in 0 until n) {
        var minj = i
        for (j in i until n) {
            if (c2.num(j) < c2.num(minj)) {
                minj = j
            }
        }
        val temp = c2[minj]
        c2[minj] = c2[i]
        c2[i] = temp
    }

    for (i in 0 until n) {
        if (c[i] != c2[i]) {
            c2Stable = false
        }
    }

    println(c.joinToString(prefix = "", postfix = "", separator = " "))
    println(if (cStable) "Stable" else "Not stable")
    println(c2.joinToString(prefix = "", postfix = "", separator = " "))
    println(if (c2Stable) "Stable" else "Not stable")
}
