fun main(args: Array<String>) {
    abc113c()
}

fun abc113c() {
    val (n, m) = readLine()!!.split(" ").map { it.toLong() }
    val pyList = (1..m).map { readLine()!!.split(" ") }
        .mapIndexed { index, list -> Triple(index.toLong(), list[0], list[1]) }
        .sortedBy { triple -> triple.third.toLong() }

    val addedCount: MutableMap<String, Long> = mutableMapOf()
    val answer = pyList.map { triple: Triple<Long, String, String> ->
        val count = (addedCount[triple.second] ?: 0) + 1
        addedCount[triple.second] = count
        Triple(
            triple.first,
            triple.second.padStart(6, '0'),
            count.toString().padStart(6, '0')
        )
    }.sortedBy { it.first }.map { it.second + it.third }

    println(answer.joinToString(separator = System.lineSeparator()))
}
