import java.io.PrintWriter


private data class City(var index: Int = 0, var prov: Int = 0, var year: Int = 0, var label: String = "")

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

    val d = Array(n) { mutableListOf<City>() }
    for (i in 0 until m) {
        val (p, y) = readLine()!!.split(" ").map { it.toInt() }
        d[p - 1].add(City(index = i, year = y))
    }

    for ( i in 0 until n) {
        d[i].sortBy{ it.year }
        for ( j in 0 until d[i].size) {
            d[i][j].label = "%06d%06d".format(i+1, j+1)
        }
    }

    val ans = d.toMutableList().flatten().sortedBy { it.index }


    val out = PrintWriter(System.out)
    out.println(ans.map { it.label }.joinToString("\n"))
    out.flush()
}