data class Card(val mark: String, val number: Int)

fun main(args: Array<String>) {
    val array1 = Array<Card>(readLine()?.toInt() ?: 0) {
        val input = readLine()
            ?.split(" ".toRegex())
            ?.toTypedArray()
            ?: arrayOf<String>()
        Card(input[0], input[1].toInt())
    }
    val array2 = array1.clone()
    array1.mergeSort()
    array2.qSort(0, array2.lastIndex)
    println(
        if (array1.contentEquals(array2)) {
            "Stable"
        } else {
            "Not stable"
        }
    )
    println(
        array2.joinToString("\n") {
            "${it.mark} ${it.number}"
        }
    )
}

fun Array<Card>.qSort(p: Int, r: Int) {
    if (p < r) {
        val mid = partition(p, r)
        qSort(p, mid - 1)
        qSort(mid + 1, r)
    }
}

fun Array<Card>.partition(p: Int, r: Int): Int {
    val x = this[r]
    var i = p - 1
    for (j in p until r) {
        if (this[j].number <= x.number) {
            i++
            swap(i, j)
        }
    }
    swap(i + 1, r)
    return i + 1
}

fun Array<Card>.mergeSort(): Int {
    return this.mergeSort(0, this.size)
}

fun Array<Card>.mergeSort(left: Int, right: Int): Int {
    var cnt = 0
    if (left + 1 < right) {
        val mid = (left + right) / 2
        cnt += this.mergeSort(left, mid)
        cnt += this.mergeSort(mid, right)
        cnt += this.merge(left, mid, right)
    }
    return cnt
}

fun Array<Card>.merge(left: Int, mid: Int, right: Int): Int {
    var cnt = 0
    val array1 = Array((mid - left) + 1) {
        Card("S", Int.MAX_VALUE)
    }
    val array2 = Array((right - mid) + 1) {
        Card("S", Int.MAX_VALUE)
    }
    for (i in 0 until array1.size - 1) {
        array1[i] = this[left + i]
    }
    for (i in 0 until array2.size - 1) {
        array2[i] = this[mid + i]
    }
    var i = 0
    var j = 0
    for (k in left until right) {
        this[k] = if (compare(array1[i], array2[j])) {
            array1[i++]
        } else {
            array2[j++]
        }
        cnt++
    }
    return cnt
}

fun compare(card1: Card, card2: Card): Boolean {
    return card1.number <= card2.number
}

fun Array<Card>.swap(i: Int, j: Int) {
    val tmp = this[i]
    this[i] = this[j]
    this[j] = tmp
}
