fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val list: List<String> = readLine()!!.split(" ").map { it.toString() }
    isStable(bubbleSort(list.toTypedArray(),n),selectionSort(list.toTypedArray(),n),n)
}
fun selectionSort(A:Array<String>, N:Int):Array<String>
{
    var tmp:String
    for (i in (0..(N - 1))) {
        var minj :Int= i
        for (j in (i .. (N - 1)))
        {
            if (A[j][1] < A[minj][1])
            {
                minj = j
            }
        }
        if (A[minj] != A[i])
        {
            tmp = A[minj]
            A[minj] = A[i]
            A[i] =tmp
        }
    }
    println(A.joinToString(" "))
    return A
}

fun bubbleSort(A:Array<String>, N:Int):Array<String>
{
     // N 個の要素を含む 0-オリジンの配列 A
    var flag:Boolean = true// 逆の隣接要素が存在する
    var tmp:String

    while(flag) {
        flag = false
        for (j in ((N - 1) downTo 1))
        {
            if (A[j][1] < A[j - 1][1])
            {
                tmp = A[j - 1]
                A[j - 1] = A[j]
                A[j] = tmp
                flag = true
            }
        }
     }
    println(A.joinToString(" "))
    println("Stable")
    return A
}
fun insertionSort(A:IntArray, N:Int) // N個の要素を含む0-オリジンの配列A
{
    var v:Int
    println(A.joinToString(" "))
    for (i in (1..(N - 1))) {
        v = A[i]
        var j:Int = i - 1
        while ((j >= 0) && (A[j] > v)) {
            A[j + 1] = A[j]
            j--
        }
        A[j + 1] = v
        println(A.joinToString(" "))
    }
}

fun isStable(A:Array<String>, B:Array<String>,N:Int)
{
    for (i in (0..(N-1)))
    {
       if (A[i] != B[i])
        {
            println("Not stable")
            return
        }
    }
    println("Stable")
    return
}
