N = gets.to_i
aOrig = gets.split

a = Marshal.load(Marshal.dump(aOrig))
N.times do |i|
    (N - 1).downto(i + 1) do |j|
        if a[j][1] < a[j - 1][1] then
            tmp = a[j]
            a[j] = a[j - 1]
            a[j - 1] = tmp
        end
    end
end
puts a.join(' ')
puts "Stable"

a = Marshal.load(Marshal.dump(aOrig))
N.times do |i|
    minJ = i
    i.upto(N - 1) do |j|
        minJ = j if a[j][1] < a[minJ][1]
    end
    if minJ != i then
        tmp = a[i]
        a[i] = a[minJ]
        a[minJ] = tmp
    end
end
puts a.join(' ')

na = aOrig.map {|aa| aa[1]}
repeaters = []
N.times do |i|
    (i + 1).upto(N - 1) do |j|
        repeaters.push([i, j].sort) if na[i] == na[j]
    end
end
isStable = true
repeaters.each do |r|
    isStable = false if a.find_index(aOrig[r[0]]) > a.find_index(aOrig[r[1]])
end
puts isStable ? "Stable" : "Not stable"

