fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map { it.toInt() }

    val cities = (0 until m).map { i ->
        val (p, y) = readLine()!!.split(' ').map { it.toInt() }
        Triple(i, p, y)
    }.sortedBy { it.third }

    val counter = IntArray(n) { 0 }

    val ids = Array(m) { "" }

    cities.forEach {
        val i = it.first
        val p = it.second
        val x = ++counter[p - 1]
        ids[i] = p.toString().padStart(6, '0') + x.toString().padStart(6, '0')
    }

    ids.forEach {
        println(it)
    }

}