def bubbleSort c, n
    for i in 0...n
        for j in (i...n).to_a.reverse
            if c[j][1] < c[j - 1][1]
                temp = c[j]
                c[j] = c[j - 1]
                c[j - 1] = temp
            end
        end
    end
end

def selectionSort c, n
    for i in 0...n
        minj = i
        for j in i...n
            minj = j if c[j][1] < c[minj][1]
        end
        temp = c[i]
        c[i] = c[minj]
        c[minj] = temp
    end
end

def checkOrder arr
    strings = Array.new(11){""}
    arr.each{|card| strings[card[1].to_i] += card[0]}
    return strings
end

n = gets.to_i
arr = gets.chomp.split

arr2 = arr.dup
bubbleSort(arr2, n)
puts arr2.join(" ")
puts (checkOrder(arr) == checkOrder(arr2)) ? "Stable" : "Not stable"

arr2 = arr.dup
selectionSort(arr2, n)
puts arr2.join(" ")
puts (checkOrder(arr) == checkOrder(arr2)) ? "Stable" : "Not stable"