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 map: Map[Int, String] =
    (1 to m)
      .map(i => (i, readLine.split(" ").map(_.toInt)))
      .groupBy { case (_, Array(p, y)) => p }
      .flatMap {
        case (p, s) =>
          s.sortBy { case (id, Array(p, y)) => y }
            .view
            .zip(Stream.from(1))
            .map {
              case ((id, Array(p, y)), index) => (id, convert(p, index))
            }
      }

  (1 to m).view.map(map).foreach(println)

}