fun intList() = readLine()?.split(" ")?.map(String::toInt) ?: TODO()
fun longList() = readLine()?.split(" ")?.map(String::toLong) ?: TODO()
fun main(args: Array<String>) {
    val (n, m) = intList()
    val array1 = Array<MutableList<Long>>(n + 1) { mutableListOf() }
    val array2 = Array<HashMap<Long, Int>>(n + 1) { hashMapOf() }
    val ps = mutableListOf<Pair<Long, Long>>()
    repeat(m) {
        val (p, y) = longList()
        array1[p.toInt()].add(y)
        ps.add(Pair(p, y))
    }
    repeat(n + 1) { i ->
        array1[i].sort()
        array1[i].forEachIndexed { j, y ->
            array2[i][y] = j
        }
    }
    buildString {
        ps.forEach {
            appendln("%06d%06d".format(it.first, array2[it.first.toInt()][it.second]!! + 1))
        }
    }.let {
        println(it.trimIndent())
    }
}
