object Main extends App {
  val (n, m) = readLine.split(" ").map(_.toInt) match {
    case Array(n, m) => (n, m)
  }

  def convert(p: Int, order: Int) = f"${p}%06d${order}%06d"

  val lines: Seq[(Int, Int, Int)] = (1 to m).map(id =>
    readLine.split(" ").map(_.toInt) match { case Array(p, y) => (id, p, y) })

  def order(t1: (Int, Int, Int), t2: (Int, Int, Int)): Boolean =
    if (t1._2 == t2._2) t1._3 < t2._3 else t1._2 < t2._2

  var currentP = 1
  var currentIndex = 0

  def next(t: (Int, Int, Int)) = {
    if (t._2 == currentP) currentIndex = currentIndex + 1 else currentIndex = 1
    currentP = t._2
    (t._1, convert(t._2, currentIndex))
  }

  lines
    .sortWith(order)
    .map(next)
    .sortBy(_._1)
    .foreach(t => println(t._2))

}
