class Card
  def initialize(mark, number)
    @mark = mark
    @number = number
  end
  attr_accessor :mark, :number

  def to_s
    "#{mark} #{number}"
  end
end

def partition(array, p, r)
  x = array[r].number
  i = p - 1
  p.upto(r - 1) do |index|
    if array[index].number <= x
      i += 1
      array[i], array[index] = array[index], array[i]
    end
  end
  array[r], array[i + 1] = array[i + 1], array[r]
  i + 1
end

def quick_sort(array, p, r)
  if p < r
    q = partition array, p, r
    quick_sort array, p, q - 1
    quick_sort array, q + 1, r
  end
  array
end

def bubble_sort(array, n)
  n.times do |i|
    (n - 1).downto(i + 1) do |j|
      if array[j].number < array[j - 1].number
        array[j], array[j - 1] = array[j - 1], array[j]
      end
    end
  end
  array
end

def stable?(bubble, sorted)
  bubble.each_with_index do |element, index|
    return false if element.mark != sorted[index].mark
  end
  true
end

n = gets.to_i
input_array = []
n.times do
  input = gets.split(' ')
  input_array << Card.new(input[0], input[1])
end

input_array2 = Marshal.load(Marshal.dump(input_array))
bubble = bubble_sort input_array, n
quick = quick_sort input_array2, 0, n - 1

if stable? bubble, quick
  puts 'Stable'
else
  puts 'Not stable'
end

puts quick.map(&:to_s)
