"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 lines = input.split('\n');

  var _splitNum = splitNum(lines.shift()),
      _splitNum2 = _slicedToArray(_splitNum, 2),
      N = _splitNum2[0],
      M = _splitNum2[1];

  var ps = new Array(N + 1).fill(null).map(function (_) {
    return [];
  });
  var ms = []; // generate object for each 市.

  for (var i = 0; i < M; i++) {
    var _splitNum3 = splitNum(lines[i]),
        _splitNum4 = _slicedToArray(_splitNum3, 2),
        P = _splitNum4[0],
        Y = _splitNum4[1];

    var mobj = {
      P,
      Y,
      newi: 0
    };
    ps[P].push(mobj);
    ms.push(mobj);
  } // sort 市s in each 県.


  var _iteratorNormalCompletion = true;
  var _didIteratorError = false;
  var _iteratorError = undefined;

  try {
    for (var _iterator = ps[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
      var parr = _step.value;
      parr.sort(function (a, b) {
        return a.Y - b.Y;
      }); // annotate each object with new index.

      var newi = 1;
      var _iteratorNormalCompletion2 = true;
      var _didIteratorError2 = false;
      var _iteratorError2 = undefined;

      try {
        for (var _iterator2 = parr[Symbol.iterator](), _step2; !(_iteratorNormalCompletion2 = (_step2 = _iterator2.next()).done); _iteratorNormalCompletion2 = true) {
          var p = _step2.value;
          p.newi = newi++;
        }
      } catch (err) {
        _didIteratorError2 = true;
        _iteratorError2 = err;
      } finally {
        try {
          if (!_iteratorNormalCompletion2 && _iterator2.return != null) {
            _iterator2.return();
          }
        } finally {
          if (_didIteratorError2) {
            throw _iteratorError2;
          }
        }
      }
    } // emit results.

  } catch (err) {
    _didIteratorError = true;
    _iteratorError = err;
  } finally {
    try {
      if (!_iteratorNormalCompletion && _iterator.return != null) {
        _iterator.return();
      }
    } finally {
      if (_didIteratorError) {
        throw _iteratorError;
      }
    }
  }

  var pad6l = function pad6l(str) {
    return `000000${str}`.slice(-6);
  };

  for (var _i2 = 0; _i2 < ms.length; _i2++) {
    var m = ms[_i2];
    console.log(pad6l(m.P) + pad6l(m.newi));
  }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

function splitNum(line) {
  return line.split(/\s+/).map(function (n) {
    return parseInt(n);
  });
}


Measured memory_bytes: 76420