(defn input []
  (let [tmp (->> (clojure.string/split (read-line) #"\s")
              (mapv #(Integer/parseInt %)))]
    (vector tmp
      (->> (repeatedly (second tmp) read-line)
        (map #(clojure.string/split % #"\s"))
        (mapv (partial mapv #(Integer/parseInt %)))))))

(defn ID [[[N M] cities]]
  (let [tmp (->> cities
              (group-by first)
              (map
                #(array-map
                   (first %)
                   (sort (map second (second %)))))
              (apply merge))]
    (->> cities
      (map (fn [[P Y]] (str
                         (format "%06d" P)
                         (->> (.indexOf (tmp P) Y)
                           inc
                           (format "%06d\n")))))
      (apply str))))


(->> (input)
  ID
  println)