def BubbleSort(c, n)
  for i in 0..n-1
    (n-1).downto(i+1){|j|
      c[j], c[j-1] = c[j-1], c[j] if c[j].value < c[j-1].value
    }
  end
end

def SelectionSort(c, n)
  for i in 0..n-1
    minj = i
    for j in i..n-1
      minj = j if c[j].value < c[minj].value
    end
    c[i], c[minj] = c[minj], c[i]
  end
end

class Card
  attr_accessor :value, :key
  def initialize(k, v)
    @key = k
    @value = v
  end
end
n = gets.to_i
c = Array.new(n)
i = 0
gets.split.each{|s|
  tmp = s.split("")
  c[i] = Card.new(s, tmp[1].to_i)
  i += 1
}

c1 = c.clone
c2 = c.clone
BubbleSort(c1, n)
s1 = ""
0.upto(n-1){|j|
  s1 << c1[j].key
  s1 << " " if j < n-1
}
printf "%s\nStable\n", s1;

SelectionSort(c2, n)
s2 = ""
0.upto(n-1){|j|
  s2 << c2[j].key
  s2 << " " if j < n-1
}
printf "%s\n", s2
if s1 == s2 then
  printf "Stable\n"
else
  printf "Not stable\n"
end