data class City(
    val index: Int,
    val p: Int,
    val y: Int
) {
    var order = -1

    val no: String
        get() = "${p.toString().padStart(6, '0')}${order.toString().padStart(6, '0')}"
}

fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map(String::toInt)
    val cities = Array<City>(m) {
        val (p, y) = readLine()!!.split(" ").map(String::toInt)
        City(it, p, y)
    }
    val partByP = mutableMapOf<Int, MutableList<City>>()
    cities.forEach {
        val c = partByP[it.p]
        if (c == null) {
            partByP[it.p] = mutableListOf(it)
        } else {
            c.add(it)
        }
    }
    partByP.forEach {
        it.value.sortBy { c -> c.y }
        it.value.forEachIndexed { i, c -> c.order = i + 1 }
    }
    cities.forEach { println(it.no) }
}
