
fun main(args : Array<String>) {
    val (N, M) = readLine()!!.split(" ").map { it.toInt() }
    val pAndY = mutableListOf<Triple<Int, Int, Int>>()
    (1..M).forEachIndexed { index, i ->
        val (p, y) = readLine()!!.split(" ").map { it.toInt() }
        val pair = Triple(index, p, y)
        pAndY.add(pair)
    }

    pAndY.sortBy { it.third }

    val nums : Array<String?> = Array(M) { init -> null }
    val pToCountMap : MutableMap<Int, Int> = mutableMapOf()
    pAndY.forEach {
        val index = it.first
        val p = it.second
        val preCount = pToCountMap.get(p)
        var count: Int
        if (preCount == null) {
            count = 1
        } else {
            count = preCount + 1
        }
        pToCountMap.set(p, count)

        val num = p.toString().padStart(6, '0') + count.toString().padStart(6, '0')
        nums[index] = num
    }

    nums.forEach {
        println(it!!)
    }
}
