count = 0
n = gets.chomp.to_i

cards = gets.split(" ")
suit,nums = cards.map{|x|x[0]},cards.map{|x|x[1].to_i}
cards = suit.zip(nums)
array = Marshal.load(Marshal.dump(cards))

i=0
while i<n
  j = n-1
  while j > i
    if array[j][1] < array[j-1][1]
      array[j],array[j-1] = array[j-1],array[j]
      count = count+1
    end  
    j = j-1
  end
  i=i+1
end

i=0
while i < n 
  printf("%s%d",array[i][0],array[i][1])
  if i+1 != n
  print " "
  end
  i = i+1
end

print "\n"
print "Stable"
print "\n"

array2 = Marshal.load(Marshal.dump(cards))
i = 0
while i<n
  j = i+1
  min = i
  while j<n
    if array2[min][1] > array2[j][1]
      min = j
    end  
    j = j+1
  end
  if min != i
  array2[min],array2[i] = array2[i],array2[min]
  count = count + 1
  end
  i=i+1
end

i=0
while i < n 
  printf("%s%d",array2[i][0],array2[i][1])
  if i+1 != n
  print " "
  end
  i = i+1
end

i,flag = 0,true
while i < n 
  flag = false if array[i][0] != array2[i][0]
  i = i+1
end

print "\n"
printf flag == true ? "Stable":"Not stable"
print "\n"