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

import scala.collection.mutable.ArrayBuffer

case class City(prefecture: Int, year: Int, index: Int) {
  var order: Int = -1
}

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[City]
    }
    val cities = Array.fill(m) {
      in.readLine().split("\\s+").map(_.toInt) match {
        case Array(p, y) =>
          val city = City(p - 1, y, prefectures(p - 1).size)
          prefectures(p - 1) += city
          city
      }
    }

    for (p <- 0 until n) {
      prefectures(p) = prefectures(p).sortWith {
        case (a, b) => a.year < b.year
      }
      for (c <- prefectures(p).indices) {
        prefectures(p)(c).order = c
      }
    }

    for (city <- cities) {
      out.println(f"${city.prefecture + 1}%06d${city.order + 1}%06d")
    }

    out.flush()
  }
}
