class Array
  def swap(x, y)
    self[x], self[y] = self[y], self[x]
  end
end

def bubbleSort(n, a)
  bs = a.clone
  n.times{|i|
    (n-1).downto(i+1){|j|
      bs[j][1]<bs[j-1][1]&&bs.swap(j,j-1)
    }
  }
  return bs
end

def selectionSort(n, a)
  ss = a.clone
  stability = 1
  n.times{|i|
    min = i
    dup = nil
    (i..n-1).each{|j|
      ss[j][1]<ss[min][1]&&min=j
      ss[j][1]==ss[i][1]&&dup=j
    }
    (dup!=nil)&&(dup<min)&&(stability=0)
    i!=min&&a.swap(i,min)
  }
  return ss, stability
end

n = gets.to_i
a = gets.split
bs = bubbleSort(n, a)
puts a.join(" ")
puts "Stable"
ss, stability = selectionSort(n, a)
puts a.join(" ")
puts (stability == 1) ? "Stable" : "Not stable"