import java.lang.IllegalArgumentException
import java.util.*

fun main(args: Array<String>) {
    readLine()!!.toInt()
    val values = readLine()!!.split(" ").toTypedArray()

    val valuesForBubbleSort = Arrays.copyOf(values, values.size)
    bubbleSort(valuesForBubbleSort)
    printValues(valuesForBubbleSort)
    if (isStable(values, valuesForBubbleSort)) {
        println("Stable")
    } else {
        println("Not stable")
    }

    val valuesForSelectionSort = Arrays.copyOf(values, values.size)
    selectionSort(valuesForSelectionSort)
    printValues(valuesForSelectionSort)
    if (isStable(values, valuesForSelectionSort)) {
        println("Stable")
    } else {
        println("Not stable")
    }
}

fun bubbleSort(values: Array<String>) {
    val comparator = CardComparator()
    for (i in 0..values.size-1) {
        for (j in values.size-1 downTo i+1) {
            if (comparator.compare(values[j], values[j-1]) < 0) {
                val temp = values[j]
                values[j] = values[j-1]
                values[j-1] = temp
            }
        }
    }
}

fun selectionSort(values: Array<String>) {
    val comparator = CardComparator()
    for (i in 0..values.size-1) {
        var minJ = i
        for (j in i..values.size-1) {
            if (comparator.compare(values[j], values[minJ]) < 0) {
                minJ = j
            }
        }
        val temp = values[i]
        values[i] = values[minJ]
        values[minJ] = temp
    }
}

fun isStable(original: Array<String>, sorted: Array<String>): Boolean {
    val joinedOriginalByNumber = listOf(
        filterCards(original, 1),
        filterCards(original, 2),
        filterCards(original, 3),
        filterCards(original, 4),
        filterCards(original, 5),
        filterCards(original, 6),
        filterCards(original, 7),
        filterCards(original, 8),
        filterCards(original, 9)
    )
    val joinedSortedByNumber = listOf(
        filterCards(sorted, 1),
        filterCards(sorted, 2),
        filterCards(sorted, 3),
        filterCards(sorted, 4),
        filterCards(sorted, 5),
        filterCards(sorted, 6),
        filterCards(sorted, 7),
        filterCards(sorted, 8),
        filterCards(sorted, 9)
    )
    for (i in 1..9) {
        if (joinedOriginalByNumber[i-1] != joinedSortedByNumber[i-1]) {
            return false
        }
    }

    return true
}

fun filterCards(values: Array<String>, number: Int): String {
    return values.filter { v -> v.substring(1, 2).toInt() == number }.joinToString("")
}

private fun printValues(values: Array<String>) {
    for (i in 0..values.size-1) {
        print(values[i])
        if (i != values.size-1) {
            print(" ")
        }
    }
    println()
}

class CardComparator : Comparator<String> {

    override fun compare(o1: String?, o2: String?): Int {
        if (o1 == null && o2 == null) {
            throw IllegalArgumentException("o1 and o2 are null.")
        }
        if (o1 == null) {
            throw IllegalArgumentException("o1 is null.")
        }
        if (o2 == null) {
            throw IllegalArgumentException("o2 is null.")
        }
        if (o1.length != 2) {
            throw IllegalArgumentException("o1 [$o1] is an invalid format.")
        }
        if (o2.length != 2) {
            throw IllegalArgumentException("o2 [$o2] is an invalid format.")
        }

        val num1 = o1.substring(1, 2).toInt(10)
        val num2 = o2.substring(1, 2).toInt(10)

        return num1 - num2
    }

}

