import java.util.*

class Card(private val s: String) {
    val suits = s[0]
    val value = s[1].toInt()

    override fun toString(): String {
        return s
    }
}

fun bubbleSort(C: Array<Card>): Array<Card> {
    for (i in C.indices) {
        for (j in C.size - 1 downTo i + 1) {
            if (C[j].value < C[j - 1].value) {
                C[j] = C[j - 1].also { C[j - 1] = C[j] }
            }
        }
    }
    return C
}

fun selectionSort(C: Array<Card>): Array<Card> {
    for (i in C.indices) {
        var minj = i
        for (j in i until C.size) {
            if (C[j].value < C[minj].value) {
                minj = j
            }
        }
        C[i] = C[minj].also { C[minj] = C[i] }
    }
    return C
}

fun whatNumber(target: Card, cards: Array<Card>): Int {
    var n = 0
    for (card in cards) {
        if (target.value == card.value) {
            n++
            if (target.suits == card.suits) {
                return n
            }
        }
    }
    return n
}

fun isStable(original: Array<Card>, sorted: Array<Card>): Boolean {
    for (card in original) {
        val n = whatNumber(card, original)
        val m = whatNumber(card, sorted)
        if (n != m) {
            return false
        }
    }
    return true
}

fun main(args: Array<String>) {
    val scanner = Scanner(System.`in`)
    val N = scanner.nextInt()
    val list = mutableListOf<Card>()
    for (i in 0 until N) {
        list.add(Card(scanner.next()))
    }
    val barr = bubbleSort(list.toTypedArray())
    println(barr.joinToString(" "))
    println(if (isStable(list.toTypedArray(), barr)) "Stable" else "Not stable")
    val sarr = selectionSort(list.toTypedArray())
    println(sarr.joinToString(" "))
    println(if (isStable(list.toTypedArray(), sarr)) "Stable" else "Not stable")
}

