import scala.io.StdIn.{readInt, readLine}

final case class Card(suit: String, value: Int)

object Main extends App {
  import QuickSort.quickSort
  import MergeSort.mergeSort

  val n     = readInt()
  val lines = Iterator.fill(n)(readLine())

  val cardsA = lines
    .map { _.split(" ") }
    .map {
      case Array(suit, v) => Card(suit, v.toInt)
    }
    .toArray

  val cardsB = cardsA.clone

  quickSort(cardsA)
  mergeSort(cardsB)

  println(if (cardsA sameElements cardsB) "Stable" else "Not stable")
  cardsA.foreach {
    case Card(suit, value) => println(s"$suit $value")
  }
}

object QuickSort {
  def quickSort(xs: Array[Card]): Unit = {

    def run(p: Int, r: Int): Unit = {
      if (p < r) {
        val q = partition(xs, p, r)
        run(p, q - 1)
        run(q + 1, r)
      }
    }

    run(0, xs.length - 1)
  }

  private def partition(xs: Array[Card], p: Int, r: Int): Int = {
    val x = xs(r).value
    var i = p - 1
    var j = p
    while (j < r) {
      if (xs(j).value <= x) {
        i += 1
        swap(xs, i, j)
      }
      j += 1
    }

    val q = i + 1
    swap(xs, q, r)
    q
  }

  private def swap[A](xs: Array[A], a: Int, b: Int): Unit = {
    val temp = xs(a)
    xs(a) = xs(b)
    xs(b) = temp
  }
}

object MergeSort {
  private val Max: Int       = 100000
  private val Sentinel: Card = Card("", 2000000000)

  def mergeSort(xs: Array[Card]): Int = {

    val ls = new Array[Card](Max / 2 + 2)
    val rs = new Array[Card](Max / 2 + 2)

    def run(left: Int, right: Int): Int = {
      val m = right - left
      if (m <= 1) 0
      else {
        val mid  = (left + right) / 2
        val cnt1 = run(left, mid)
        val cnt2 = run(mid, right)
        merge(left, mid, right)
        cnt1 + cnt2 + m
      }
    }

    def merge(left: Int, mid: Int, right: Int): Unit = {
      val n1 = mid - left
      val n2 = right - mid
      Array.copy(xs, left, ls, 0, n1)
      Array.copy(xs, mid, rs, 0, n2)
      ls(n1) = Sentinel
      rs(n2) = Sentinel
      var i  = 0
      var j  = 0
      var k  = left
      while (k < right) {
        if (ls(i).value <= rs(j).value) {
          xs(k) = ls(i)
          i += 1
        } else {
          xs(k) = rs(j)
          j += 1
        }
        k += 1
      }
    }

    run(0, xs.length)
  }
}

