fun main(args : Array<String>) {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val cities = mutableListOf<City>()

    repeat(m) { idx ->
        val (p, y) = readLine()!!.split(" ").map { it.toInt() }
        cities.add(City(idx, p, y, ""))
    }

    cities.sortWith(Comparator { c1, c2 ->
        when {
            c1.prefecture < c2.prefecture -> -1
            c1.prefecture > c2.prefecture -> 1
            c1.year < c2.year -> -1
            c1.year > c2.year -> 1
            else -> 0
        }
    })

    var prevP = 0
    var yIdx = 1
    cities.forEach { c ->
        if (c.prefecture != prevP) {
            prevP = c.prefecture
            yIdx = 1
        }
        c.num = c.prefecture.toString().padStart(6, '0') + yIdx.toString().padStart(6, '0')
        yIdx++
    }

    cities.sortedBy { it.idx }.forEach { println(it.num) }
}

data class City(val idx: Int, val prefecture: Int, val year: Int, var num: String)