class Card
  def initialize(mark, number)
    @mark = mark
    @number = number.to_i
  end

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

  attr_accessor :number, :mark
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 merge(left_array, right_array)
  return_array = []
  left_index, right_index = 0, 0
  left_array << Card.new('', 10**9)
  right_array << Card.new('', 10**9)
  0.upto(left_array.length + right_array.length - 3) do
    if left_array[left_index].number < right_array[right_index].number
      return_array << left_array[left_index]
      left_index += 1
    else
      return_array << right_array[right_index]
      right_index += 1
    end
  end
  return_array
end

def merge_sort(target_array)
  right = target_array.length
  mid = target_array.length / 2
  left_array = target_array[0...mid]
  right_array = target_array[mid...right]
  return target_array if target_array.length == 1
  merge(merge_sort(left_array), merge_sort(right_array))
end

def stable?(merge, sorted)
  merge.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))
merge = merge_sort input_array
quick = quick_sort input_array2, 0, n - 1

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

puts quick.map(&:to_s)
