import java.util.Scanner

import scala.collection.mutable.ArrayBuffer

object Main extends App {
  val sc = new Scanner(System.in)

  def nextInt(): Int = {
    sc.next.toInt
  }

  val n, m = sc.nextInt()
  var cnt = ArrayBuffer.fill(n + 1)(0)
  val ans = (for (i <- 1 to m) yield (i, nextInt(), nextInt())).sortBy { // index, pref, year
    case (_, _, year) => year
  }.map {
    case (index, pref, _) =>
      cnt(pref) += 1
      (index, "%06d%06d".format(pref, cnt(pref)))
  }.sorted
  println(ans.map(_._2).mkString("\n"))
}
