
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toString() }.toTypedArray()

    val bubbleSorted = bubbleSort(n, a)
    println(bubbleSorted.joinToString(" "))

    println("Stable")

    val insertionSorted = insertionSort(n, a)
    println(insertionSorted.joinToString(" "))

    val isStable = isStable(bubbleSorted, insertionSorted, n)
    if(isStable) {
        println("Stable")
    } else {
        println("Not stable")
    }
}

private fun isStable(first: Array<String>, second: Array<String>, n: Int):Boolean {
    for(i in 0 until n) {
        if(first[i] != second[i]) {
            return false
        }
    }
    return true
}

fun bubbleSort(n:Int, a: Array<String>):Array<String> {
    val copied = a.copyOf()

    var flag = true
    var i = 0
    while (flag) {
        flag = false
        for (j in n - 1 downTo i + 1) {
            if (copied[j].last().toInt() < copied[j - 1].last().toInt()) {
                var temp = copied[j]
                copied[j] = copied[j - 1]
                copied[j - 1] = temp
                flag = true
            }
        }
        i++
    }
    return copied
}

fun insertionSort(n:Int, a: Array<String>):Array<String> {
    val copied = a.copyOf()

    for (i in 0 until n) {
        var minj = i
        for (j in i + 1 until n) {
            if (copied[j].last().toInt() < copied[minj].last().toInt()) {
                minj = j
            }
        }
        if (i != minj) {
            val tmp = copied[i]
            copied[i] = copied[minj]
            copied[minj] = tmp
        }
    }

    return copied
}

