import java.lang.String.format

fun main(args: Array<String>) {
    val line = readLine()!!.split(' ').map { it.toInt() }
    val rank = IntArray(line[0] + 1) { 1 }
    val cities = (1..line[1]).map {
        val l = readLine()!!.split(' ').map { it.toInt() }
        Triple(it, l[0], l[1])
    }.sortedBy { it.third }
    val sb = StringBuilder()
    cities.map { Pair(it, rank[it.second]++) }
            .sortedBy { it.first.first }
            .forEach {
                sb.append(format("%06d%06d\n", it.first.second, it.second))
            }
    println(sb)
}
