def bsort (a,n)
  for i in 0...n
    j = n-1
    while j > i
      if a[j][1].ord < a[j-1][1].ord
        t = a[j]
        a[j] = a[j-1]
        a[j-1] = t
      end
      j -= 1
    end
  end
  a
end

def ssort (a,n)
  for i in 0...n
    min = i
    for j in i...n
      min = j if a[j][1].ord < a[min][1].ord
    end
    if min != i
      t = a[i]
      a[i] = a[min]
      a[min] = t
    end
  end
  a
end

n = gets.to_i
a = gets.split
b = bsort(a.clone, n)
c = ssort(a.clone, n)

puts b.join(" ")
puts "Stable"

puts c.join(" ")
if b == c
  puts "Stable"
else
  puts "Not stable"
end

