(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(declaim (inline read-line-into))
(defun read-line-into (buf-str &optional (in *standard-input*) (terminate-char #\space))
  (declare (simple-base-string buf-str))
  (loop for ch of-type base-char =
           #-swank (code-char (read-byte in nil #\Newline))
           #+swank (read-char in nil #\Newline)
        for idx = 0 then (1+ idx)
        until (char= ch #\Newline)
        do (setf (aref buf-str idx) ch)
        finally (setf (aref buf-str idx) terminate-char)
                (return buf-str)))

(defmacro split-and-bind (arg-lst string &body body)
  (let ((pos1 (gensym "POS"))
	(pos2 (gensym "POS"))
	(str (gensym "STR")))
    (labels ((expand (arg-lst &optional (init-pos1 t))
	       (if (null arg-lst)
		   body
		   `((let* ((,pos1 ,(if init-pos1 0 `(1+ ,pos2)))
			    (,pos2 (position #\space ,str :start ,pos1 :test #'char=))
			    (,(car arg-lst) (parse-integer ,str :start ,pos1 :end ,pos2)))
		       ,@(expand (cdr arg-lst) nil))))))
      `(let ((,str ,string))
         (declare (string ,str))
	 ,@(expand arg-lst)))))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 4 7 8 15 16 31 32 62 63 64)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

;; Hauptteil

(defstruct city
  (year 0 :type uint31)
  (prefecture 0 :type uint31)
  (version 0 :type uint31))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (m (read))
         (p-table (make-array (list (1+ n)) :element-type 'list :initial-element nil))
         (city-table (make-array (list m) :element-type 'list :initial-element nil))
         (buf (make-string 21 :element-type 'standard-char :initial-element #\space)))
    ;; node := (prefecture year version)
    (dotimes (city-idx m)
      (split-and-bind (prefecture year) (read-line-into buf *standard-input* #\space)
        (let ((node (make-city :prefecture prefecture :year year)))
          (push node (aref p-table prefecture))
          (setf (aref city-table city-idx) node))))
    (loop for p-idx from 1 to n
          do (setf (aref p-table p-idx)
                   (sort (the list (aref p-table p-idx)) #'< :key #'city-year))
             (loop for node in (aref p-table p-idx)
                   for version from 1
                   do (setf (city-version node) version)))
    (dotimes (city-idx m)
      (format t "~6,'0D~6,'0D~%"
              (city-prefecture (aref city-table city-idx))
              (city-version (aref city-table city-idx))))))

#-swank(main)


Measured memory_bytes: 79840