import java.io.PrintWriter

fun main(args: Array<String>) {
    val reader = System.`in`.bufferedReader()
    val (N, M) = reader.readLine()!!.split(" ").map { Integer.parseInt(it) }
    val pw = PrintWriter(System.out)

    var p = mutableMapOf<Int, Int>()
    var y = mutableMapOf<Int, Int>()
    var yd = mutableMapOf<Int, MutableList<Int>>()

    for (i in 1..M) {
        val (Pi, Yi) = reader.readLine()!!.split(" ").map { Integer.parseInt(it) }
        p[i] = Pi
        y[i] = Yi
        if (yd.containsKey(Pi)) {
            yd[Pi]!!.add(Yi)
        } else {
            yd[Pi] = mutableListOf(Yi)
        }
    }

    var ydid = mutableMapOf<Int, Int>()
    for (i in yd.keys) {
        var num = 1
        for (j in yd[i]!!.sorted()) {
            ydid[j] = num
            num = num.inc()
        }
    }
//    var res = mutableListOf<String>()
    for (i in 1..M) {
//        res.add(p[i].toString().padStart(6, '0') + ydid[y[i]].toString().padStart(6, '0'))
//        val pid = "%06d".format(p[i])
//        val yid = "%06d".format(ydid[y[i]])
//        pw.println("%s%s".format(pid, yid))
        pw.println(p[i].toString().padStart(6, '0') + ydid[y[i]].toString().padStart(6, '0'))
    }
    pw.flush()
}