def bubble_sort(n, ary)

  index_last = n - 2

  while index_last >= 0

    for i in 0 .. index_last
      if ary[i][1] > ary[i + 1][1]
        ary[i], ary[i + 1] = ary[i + 1], ary[i]
      end
    end

    index_last -= 1
  end

  return ary
end

def selection_sort(n, ary)

  for i in 0 .. n - 2

    min = ary[i][1]
    min_index = i

    for j in i .. n - 1
      if min > ary[j][1]
        min = ary[j][1]
        min_index = j
      end
    end

    if ary[i][1] != ary[min_index][1]
      ary[i], ary[min_index] = ary[min_index], ary[i]
    end
  end

  return ary
end

def stable? (ary, org)

  (ary.size - 1).times do |i|
    if ary[i][1] == ary[i+1][1]
      if org.index(ary[i]) > org.index(ary[i+1])
        return "Not stable"
      end
    end
  end

  return "Stable"
end

num = gets.to_i
ary_original = gets.split
aryB = Marshal.load(Marshal.dump(ary_original)) #aryB: array for Bubble Sort
aryS = Marshal.load(Marshal.dump(ary_original)) #aryS: array for Selection Sort

puts bubble_sort(num, aryB).join(" "), stable?(aryB, ary_original)
puts selection_sort(num, aryS).join(" "), stable?(aryS, ary_original)

