def selectSort(a, n)
    for i in 0..n-1
        minj = i
        for j in i..n-1
            if a[j][1].to_i < a[minj][1].to_i
                minj = j
            end
        end
        next if i == minj 
        k = a[i]
        a[i] = a[minj]
        a[minj] = k
    end
    return a
end

def bubbleSort(a, n)
    flag = true
    while flag == true
        flag = false
        for j in (-n+1)..-1
            if a[-j][1].to_i < a[-j-1][1].to_i then
                k = a[-j]
                a[-j] = a [-j-1]
                a [-j-1] = k
                flag = true
            end
        end
    end
    return a
end

n = gets.to_i
a = gets.split
k = a.dup
bubbleSort_ary = bubbleSort(k,n)
puts bubbleSort_ary.join(" ")
puts "Stable"
k = a.dup
selectSort_ary = selectSort(k,n)
puts selectSort_ary.join(" ")
puts (bubbleSort_ary == selectSort_ary ? "Stable": "Not stable")
