import java.util.*

fun main(args: Array<String>){

    var (N,M) = readLine()!!.split(" ").map{it.toInt()}

    var list = Array(N+1){ mutableListOf<Int>()}
    var P = IntArray(M)
    var Y = IntArray(M)

    for(i in 0 until M){
        var (p,y) = readLine()!!.split(" ").map{it.toInt()}
        P[i] = p
        Y[i] = y

        list[p].add(y)
    }

    for(i in 0..N){
        list[i].sort()
    }

    for(i in 0 until M){
        println("%06d".format(P[i]) + "%06d".format(list[P[i]].binarySearch(Y[i]) +1))
    }


}
