fun main(args: Array<String>) {
    val (n, m) = readInputLine().split(" ").map { it.toInt() }
    // (pref, year)
    val cities = mutableListOf<Pair<Int, Int>>()
    // (pref, years)
    val map = mutableMapOf<Int, MutableList<Int>>()
    
    for (i in 1..m) {
        val (p, y) = readInputLine().split(" ").map { it.toInt() }
        cities.add(Pair(p, y))
        
        val prefInfo = map.get(p) ?: mutableListOf<Int>()
        prefInfo.add(y)
        map.put(p, prefInfo)
    }
    
    // 各県の年数をソート
    map.forEach { it.value.sort() }
    
    for (city in cities) {
        val prefInfo = map.get(city.first)!!
        println(city.first.toString().padStart(6, '0') + (prefInfo.binarySearch(city.second) + 1).toString().padStart(6, '0'))
    }
}

fun readInputLine(): String {
    return readLine()!!
}
