import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val N = sc.nextInt()
    val M = sc.nextInt()
    val ps: Array<Array<Int>?> = arrayOfNulls(M)

    for (i in ps.indices) {
        ps[i] = arrayOf(sc.nextInt(), sc.nextInt(), i)
    }
    ps.sortBy { it!![1] }

    val mp = Array(N + 10) { 0 }
    val res: Array<String?> = arrayOfNulls(M)

    for (l in ps) {
        val p = l!![0]
        val c = mp[p] + 1
        mp[p] = c

        res[l[2]] = (1000000000000L + p * 1000000L + c).toString().drop(1)
    }

    for (i in res.indices) {
        println(res[i])
    }
}
