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 }

    val sb=StringBuilder()
    cities.map {
        Pair(it,rank[it.second]++)
    }.sortedBy {
        it.first.first
    }.forEach {
        sb.append(it.first.second.toString().padStart(6,'0'))
        sb.append(it.second.toString().padStart(6,'0'))
        sb.append("\n")
    }
    println(sb)
}
