fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val cards = (0 until n).map {
        val (suit, number) = readLine()!!.split(' ')
        suit to number.toInt()
    }

    val mergeSorted = mergeSort(cards)
    val quickSorted = quickSort(cards)

    (0 until n).all {
        mergeSorted[it].first == quickSorted[it].first
    }.run {
        println(if (this) "Stable" else "Not stable")
    }

    quickSorted.forEach { println("${it.first} ${it.second}") }
}

private fun mergeSort(cards: List<Pair<String, Int>>): List<Pair<String, Int>> {

    val mutableList = cards.toMutableList()
    val leftList = Array(cards.size / 2 + 2) { "" to 0 }
    val rightList = Array(cards.size / 2 + 2) { "" to 0 }

    fun merge(left: Int, mid: Int, right: Int) {
        val leftSize = mid - left
        for (i in 0 until leftSize) {
            leftList[i] = mutableList[left + i]
        }
        leftList[leftSize] = "" to Int.MAX_VALUE

        val rightSize = right - mid
        for (i in 0 until rightSize) {
            rightList[i] = mutableList[mid + i]
        }
        rightList[rightSize] = "" to Int.MAX_VALUE

        var l = 0
        var r = 0

        for (i in left until right) {
            if (leftList[l].second <= rightList[r].second) {
                mutableList[i] = leftList[l++]
            } else {
                mutableList[i] = rightList[r++]
            }
        }

    }

    fun sort(left: Int, right: Int) {
        if (left + 1 < right) {
            val mid = (left + right) / 2
            sort(left, mid)
            sort(mid, right)
            merge(left, mid, right)
        }
    }

    sort(0, cards.size)

    return mutableList
}

private fun quickSort(cards: List<Pair<String, Int>>): MutableList<Pair<String, Int>> {

    val mutableList = cards.toMutableList()

    fun partition(p: Int, r: Int): Int {
        val x = mutableList[r]
        var i = p - 1

        for (j in p until r) {
            if (mutableList[j].second <= x.second) {
                i++
                val t = mutableList[i]
                mutableList[i] = mutableList[j]
                mutableList[j] = t
            }
        }

        val t = mutableList[i + 1]
        mutableList[i + 1] = mutableList[r]
        mutableList[r] = t

        return i + 1
    }

    fun sort(p: Int, r: Int) {
        if (p < r) {
            val q = partition(p, r)
            sort(p, q - 1)
            sort(q + 1, r)
        }
    }

    sort(0, cards.lastIndex)

    return mutableList
}
