fun main(arr:Array<String>) {
    val (n,m) = readLine()!!.split(" ").map { it.toInt() }
    val cityCount = (1..n).map { 0 }.toMutableList()
    val ans = StringBuilder()
    val city = (0 until m).map {idx -> readLine()!!.split(" ").let { City(idx, it[0].toInt(), it[1].toLong()) } }
    city.sortedBy { it.year }.forEach {
        cityCount[it.ken - 1]++
       it.num = it.ken.toString().padStart(6, '0') +  cityCount[it.ken - 1].toString().padStart(6, '0')
    }
    city.forEach { ans.appendln(it.num) }
    print(ans.toString())
}
class City(val id:Int, val ken:Int, val year:Long) {
    var num:String = ""
}