N = gets.to_i
a = gets.chomp.split
a_bubble = a.dup
a_select = a.dup
def bubble_sort(ary,num)
  flag = 1
  while flag == 1
    flag = 0
    for j in 1..num-1
      if ary[num-j][1] < ary[num-j-1][1]
        i = ary[num-j-1]
        ary[num-j-1] = ary[num-j]
        ary[num-j] = i
        flag = 1
      end
    end
  end
end
def selection_sort(ary,num)
  for i in 0..num-1
    minj = i
    for j in i..num-1
      if ary[j][1] < ary[minj][1]
        minj = j
      end
    end
    if minj != i
      k = ary[minj]
      ary[minj] = ary[i]
      ary[i] = k
    end
  end
end
def stable?(ary,s_ary)
  i = 1
  while i<= 9
    stack1 = []
    stack2 = []
    for j in 0..ary.length-1
      if ary[j][1] == "#{i}"
        stack1.push(ary[j])
      end
      if s_ary[j][1] == "#{i}"
        stack2.push(s_ary[j])
      end
    end
    if stack1 != stack2
      return "Not stable"
    end
    i += 1
  end
  "Stable"
end
bubble_sort(a_bubble,N)
selection_sort(a_select,N)
puts a_bubble.join(" ")
puts stable?(a,a_bubble)
puts a_select.join(" ")
puts stable?(a,a_select)