object Main extends App {
	case class Town(val p: Int, val y: Long)

	val Array(n, m) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
 	
 	val pN = new Array[Int](n)
 	val id = new Array[Long](m)

 	val towns = {for(i<-0 until m) yield{
 		val Array(p, y) = scala.io.StdIn.readLine.split(" ")
 		Town(p.toInt, y.toLong)
 	}}.zipWithIndex.sortBy(_._1.y)


 	for((t, i) <- towns){
 		pN(t.p - 1) += 1
 		id(i) = 1000000000000L + t.p*1000000L + pN(t.p - 1) 
 	}

 	id.foreach{z => println(z.toString.takeRight(12))}
} 