object Main extends App {
	val Array(n, m) = scala.io.StdIn.readLine.split(" ").map(_.toInt)

	val px = new Array[(Int, Long)](m)

	for(i<-0 until m){
		val Array(t1, t2) = scala.io.StdIn.readLine.split(" ")
		px(i) = (t1.toInt, t2.toLong)
	}

	var v = Set[Int]()
	var s = 1

	px.sortBy(z => (z._1, z._2)).foreach{
		z => if(v.size == 0) v += z._1
		     else if(v.apply(z._1)) s += 1
		     else s = 1
             println(f"${z._1}%06d${s}%06d")
	}

} 