class Msort
  attr_reader :arr, :count

  def initialize(arr)
    @arr = arr
    @count = 0
  end

  def exec(l=0, r=arr.length-1)
    if l < r
      mid = (r - l) / 2 + l
      exec(l, mid)
      exec(mid+1, r)
      merge(l, mid, r)
    end
  end

  def merge(left, mid, right)
    l = @arr[left..mid]
    r = @arr[mid+1..right]
    tl = l.shift
    tr = r.shift
    result = []
    loop do
      break if [tl, tr].all?(&:nil?)
      @count += 1
      if tl.nil?
        result << tr
        tr = r.shift
        next
      end
      if tr.nil?
        result << tl
        tl = l.shift
        next
      end
      if tl.number <= tr.number
        result << tl
        tl = l.shift
      else
        result << tr
        tr = r.shift
      end
    end
    (left..right).each.with_index(0) do |i, idx|
      @arr[i] = result[idx]
    end
  end

  def out
    arr.map do |c|
      "#{c.type} #{c.number}"
    end
  end
end

class Qsort
  attr_reader :arr

  def initialize(arr)
    @arr = arr
  end

  def exec(l=0, r=arr.length-1)
    if l < r
      q = partition(l, r)
      exec(l, q-1)
      exec(q+1, r)
    end
  end

  def partition(l, r)
    q = @arr[r].number
    i = l - 1
    (l..r-1).each do |j|
      if @arr[j].number <= q
        i += 1
        @arr[i], @arr[j] = @arr[j], @arr[i]
      end
    end
    @arr[i+1], @arr[r] = @arr[r], @arr[i+1]
    i+1
  end

  def out
    arr.map do |c|
      "#{c.type} #{c.number}"
    end
  end
end

class Card
  attr_reader :number, :type
  def initialize(number, type)
    @number = number
    @type = type
  end
end

n = gets.to_i
arr = []
n.times do
  t, n = gets.split
  arr << Card.new(n.to_i, t)
end
q = Qsort.new(arr.dup)
m = Msort.new(arr.dup)
q.exec
m.exec
qresult = q.out
mresult = m.out
puts qresult.join(' ') == mresult.join(' ') ? 'Stable' : 'Not stable'
qresult.each(&method(:puts))

