#!/usr/bin/ruby
# -*- coding: utf-8 -*-
class Sort
  def initialize(v)
    @n = v.length
    @a = Array.new(@n, 0)
    (0..(@n-1)).each {|i| @a[i] = v[i]}
  end


  def bubble(e,debug)
    f = @a.dup()
    0.upto(@n-1).each{|i|
      (@n-1).downto(i+1).each{|j|
        if e.call(f[j],f[j-1]) <0 then
          tmp = f[j]
          f[j] = f[j-1]
          f[j-1] = tmp
        end
      }
      puts f.map{|x| x.to_s}.join(" ") if debug
    }
    f
  end

  def selection(e,debug)
    f = @a.dup()
    0.upto(@n-1).each{|i|
      mini = i
      i.upto(@n-1).each{|j|
        if e.call(f[j], f[mini]) < 0 then
          mini = j
        end
      }
      if i != mini then
        tmp = f[i]
        f[i] = f[mini]
        f[mini] = tmp
      end
      puts f.map{|x| x.to_s}.join(" ") if debug
    }
    f
  end

  def insertion(e,debug)
    f = @a.dup()
    (0..(@n-1)).each{|i|
      key = f[i]
      j = i-1
      while j>=0 and e.call(f[j], key)>0
        f[j+1] = f[j]
        j -= 1
      end
      f[j+1]=key

      puts f.map{|x| x.to_s}.join(" ") if debug
    }
    f
  end

end

class Main
  def initialize()
    #fh = open("x.txt")
    fh = STDIN
    n = fh.gets.chomp.to_i
    #count=0
    fl = fh.gets.chomp.split
    abort if fl.length != n
    st = Sort.new(fl)
    cmp = lambda {|x,y|x.slice(1,1) <=> y.slice(1,1) }

    ans_b = st.bubble(cmp, false)
    puts ans_b.map{|x|x.to_s}.join(" ")
    puts "Stable"
    ans_s = st.selection(cmp, false)
    puts ans_s.map{|x|x.to_s}.join(" ")

    if ans_b == ans_s then
      puts "Stable"
    else
      puts "Not stable"
    end

  end
end

if $0==__FILE__ then
  Main.new()
end
#    ans = st.insertion(cmp, true)