"use strict";

function _slicedToArray(arr, i) { return _arrayWithHoles(arr) || _iterableToArrayLimit(arr, i) || _nonIterableRest(); }

function _nonIterableRest() { throw new TypeError("Invalid attempt to destructure non-iterable instance"); }

function _iterableToArrayLimit(arr, i) { var _arr = []; var _n = true; var _d = false; var _e = undefined; try { for (var _i = arr[Symbol.iterator](), _s; !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"] != null) _i["return"](); } finally { if (_d) throw _e; } } return _arr; }

function _arrayWithHoles(arr) { if (Array.isArray(arr)) return arr; }

function Main(input) {
  var args = input.split('\n');
  var args0 = args[0].split(' ');
  var sumPrefecture = +args0[0];
  var sumCity = +args0[1];
  args.shift();
  var cityList = args.map(function (item) {
    var tmpArry = item.split(' ');
    var belongPrefecture = tmpArry[0];
    var barthYear = tmpArry[1];
    return {
      pre: +belongPrefecture,
      year: +barthYear
    };
  });
  var preList = {};

  var _loop = function _loop(i) {
    preList[i.toString().padStart(6, '0')] = cityList.filter(function (item) {
      return item.pre == i;
    }).map(function (item) {
      return item.year;
    }).sort(function (a, b) {
      return a - b;
    });
  };

  for (var i = 1; i <= sumPrefecture; i++) {
    _loop(i);
  }

  Object.keys(preList).forEach(function (key, index) {
    var _iteratorNormalCompletion = true;
    var _didIteratorError = false;
    var _iteratorError = undefined;

    try {
      for (var _iterator = preList[key].entries()[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
        var _step$value = _slicedToArray(_step.value, 2),
            item = _step$value[0],
            index2 = _step$value[1];

        console.log(key + (+item + 1).toString().padStart(6, '0'));
      }
    } catch (err) {
      _didIteratorError = true;
      _iteratorError = err;
    } finally {
      try {
        if (!_iteratorNormalCompletion && _iterator.return != null) {
          _iterator.return();
        }
      } finally {
        if (_didIteratorError) {
          throw _iteratorError;
        }
      }
    }
  });
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));