def f
  n = gets.chomp.to_i
  a = gets.chomp.split
  bubble_sort(a, n)
  selection_sort(a, n)
end

def bubble_sort(a, n)
  b = a
  flag = 1
  while flag == 1
    flag = 0
    for i in 1..n-1
      j = n-i
      if a[j] < a[j-1]
        a[j-1], a[j] = a[j], a[j-1]
        flag = 1
      end
    end
  end
  puts a.join(" ")
  is_stable(b, a, n)
end

def selection_sort(a,n)
  b = a
  for i in 0..n-1
    minj = i
    for j in i..n-1
      if a[j] < a[minj]
        minj = j
      end
    end
    if i != minj
      a[i], a[minj] = a[minj], a[i]
    end
  end
  puts a.join(" ")
  is_stable(b, a, n)
end

def is_stable(in_a, out_a, n)
  for i in 0..n-1
    for j in i+1..n-1
      for a in 0..n-1
        for b in a+1..n-1
          if in_a[i][1] == in_a[j][1] && in_a[i] == out_a[b] && in_a[j] == out_a[a]
            puts "Not stable"
            return
          end
        end
      end
    end
  end
  puts "Stable"
  return
end

f
