import java.util.*

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val M = sc.next().toInt()
        val PY = (0 until M).map { Triple(it, sc.next().toInt(), sc.next().toInt()) }
            .sortedBy { it.third }
        val seq = IntArray(N)
        val ans = LongArray(M)
        PY.forEach {
            val p = it.second - 1
            seq[p]++
            ans[it.first] = (p + 1) * 1000000L + seq[p]
        }
        ans.forEach {
            pw.printf("%012d\n", it)
        }
    }
}
