import java.io.{BufferedOutputStream, BufferedReader, InputStreamReader, PrintWriter}

import scala.collection.mutable.ArrayBuffer

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val out = new PrintWriter(new BufferedOutputStream(System.out))

    val Array(n, m) = in.readLine().split("\\s+").map(_.toInt)
    val prefectures = Array.fill(n) {
      ArrayBuffer.empty[Int]
    }
    val cities = Array.fill(m) {
      in.readLine().split("\\s+").map(_.toInt) match {
        case Array(p, y) =>
          prefectures(p - 1) += y
          (p, y)
      }
    }

    val ids = for (p <- 0 until n) yield {
      prefectures(p).zipWithIndex.sortBy(_._1).map(_._2).zipWithIndex.sortBy(_._1).map(_._2 + 1)
    }

    val idCursors = Array.ofDim[Int](n)

    for (city <- cities) {
      val p = city._1
      out.println(f"${p}%06d${ids(p - 1)(idCursors(p - 1)) }%06d")
      idCursors(p - 1) += 1
    }

    out.flush()
  }
}
