fun main() {
    val (n, m) = readLine()!!.split(' ').map { it.toInt() }
    val group = (0 until m)
            .map {
                val (p, y) = readLine()!!.split(' ').map { it.toInt() }
                Triple(it, p, y)
            }
            .groupBy { it.second }

    val ids = Array<String?>(m) { null }
    for (cities in group) {
        var cnt = 0
        for ((i, p, y) in cities.value.sortedBy { it.third }) {
            cnt++
            ids[i] = "$p".padStart(6, '0') + "$cnt".padStart(6, '0')
        }
    }

    println(ids.joinToString("\n"))
}
