class Card
  def initialize(mark, value)
    @mark, @value = mark, value
  end

  def description
    "#{@mark} #{@value}"
  end

  attr_reader :value
end

def partition(a, p, r)
  x = a[r]
  i = p - 1
  p.upto(r-1).each {|j|
    if a[j].value <= x.value
      i += 1
      a[i], a[j] = a[j], a[i]
    end
  }
  a[i+1], a[r] = a[r], a[i+1]
  i+1
end

def quick_sort(a, p, r)
  return unless p < r
  q = partition(a, p, r)
  quick_sort(a, p, q-1)
  quick_sort(a, q+1, r)
end

def extract_duplicate(cards)
  dups = cards.group_by{|c| c.value}.reject{|k,v| v.one?}
  dups.keys.sort.map {|k| dups[k].map(&:description)}
end

def is_stable?(org_dup, other_dup)
  org_dup == other_dup ? "Stable" : "Not stable"
end

n = gets.to_i
a = 1.upto(n).map{
  tmp = gets.split
  Card.new tmp[0], tmp[1].to_i
}
o_dup = extract_duplicate a
quick_sort(a, 0, n - 1)
s_dup = extract_duplicate a
puts is_stable? o_dup, s_dup
puts a.map(&:description).join("\n")