import java.lang.Long.parseLong
import java.util.*

fun main(args:Array<String>) {
    val mod = 1000000007L
    var (N,M) = readLine()!!.split(' ').map(String::toInt)

    val list = Array(N+1){ mutableListOf<Pair<Int, Long>>()}
    val ans = Array(M){""}
    for (m in 0 until M) {
        val (P, Y) = readLine()!!.split(' ').map(String::toLong)
        list[P.toInt()].add(m to Y)
    }
    for ((i0,l) in list.withIndex()) {
        l.sortBy { it.second }
        for ((i1, p) in l.withIndex())
            ans[p.first] = "%06d%06d".format(i0, i1+1)
    }

    println(ans.joinToString("\n"))
}