import java.util.*

fun main(args : Array<String>) {
        val scanner = Scanner(System.`in`)
        println(inOutExec(scanner))
        }

        fun inOutExec(scanner: Scanner): String {
        val numOfPref = scanner.nextInt()
        val numOfCity = scanner.nextInt()

        val citiesIn = mutableListOf<Pair<Int, Int>>()
        repeat(numOfCity) {
        citiesIn.add(Pair(scanner.nextInt(), scanner.nextInt()))
        }

        val cityCodeMap = citiesIn
        .groupByTo(mutableMapOf()) { it.first }
        .flatMap { entry -> entry.value // List<Pair<Int, Int>>
        .sortedBy { info -> info.second }
        .mapIndexed { index, pair ->
        pair to "%06d%06d".format(pair.first, index + 1) } } // Pair<Pair<Int, Int>, String>
        .toMap()

        return citiesIn.joinToString(separator = "\n", postfix = "\n") { cityCodeMap[it]!! }
        }
