fun main(args: Array<String>) {
    readLine()
    val input = readLine()
        ?.split(" ")
        ?.toTypedArray()
        ?: arrayOf("")
    val bArray = input.clone()
    val sArray = input.clone()
    bubbleSort(bArray)
    selectionSort(sArray)
    println(bArray.joinToString(" "))
    println("Stable")
    println(sArray.joinToString(" "))
    println(
        if (sArray.contentEquals(bArray)) {
            "Stable"
        } else {
            "Not stable"
        }
    )
}

fun bubbleSort(array: Array<String>) {
    for (i in array.indices) {
        for (j in array.size - 2 downTo i) {
            if (compare(array[j], array[j+1])) {
                array.swap(j, j+1)
            }
        }
    }
}

fun selectionSort(array: Array<String>) {
    for (i in 0 until array.size - 1) {
        var min = i
        for (j in i + 1 until array.size) {
            if (compare(array[min], array[j])) {
                min = j
            }
        }
        if (min != i) {
            array.swap(i, min)
        }
    }
}

fun compare(val1: String, val2: String): Boolean {
    val num1 = val1.substring(1).toInt()
    val num2 = val2.substring(1).toInt()
    return num1 > num2
}

fun Array<String>.swap(i: Int, j: Int) {
    val tmp = this[i]
    this[i] = this[j]
    this[j] = tmp
}
