fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    var rank = IntArray(n + 1) { 1 }
    val cities=(1..m).map {
        val (p, y) = readLine()!!.split(" ").map { it.toInt() }
        return@map Triple(it, p, y)
    }.sortedBy { it.third }

    cities.map {
        Pair(
                it.first,
                it.second.toString().padStart(6, '0')
                        + rank[it.second]++.toString().padStart(6, '0'))
    }
            .sortedBy { it.first }
            .forEach { println(it.second) }
}