fun main(args: Array<String>) {
    val (N, M) = listOfInt()
    val V = Array(N) { mutableListOf<Pair<Int, Int>>() }
    repeat(M) { m ->
        val py = listOfInt()
        V[py[0] - 1].add(py[1] to m)
    }
    fun d6(n: Int) = "%06d".format(n)
    fun d12(p: Int, y: Int) = d6(p) + d6(y)
    val ans = Array(M) { "" }
    V.forEachIndexed { m, v ->
        v.sortedBy { it.first }.forEachIndexed { n, p -> ans[p.second] = d12(m + 1, n + 1) }
    }
    println(ans.joinToString(separator = "\n"))
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }
