"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; }

var fs = require('fs'),
    util = require('util');

var readFile = util.promisify(fs.readFile).bind(util);

var zerofill = function zerofill(str, n) {
  return ('0'.repeat(n) + str).slice(-n);
};

var f1 = async function f1() {
  var lines = (await readFile('/dev/stdin')).toString().split('\n');
  lines.reverse();

  var _lines$pop$split = lines.pop().split(' '),
      _lines$pop$split2 = _slicedToArray(_lines$pop$split, 2),
      N = _lines$pop$split2[0],
      M = _lines$pop$split2[1];

  var data = [];
  var _P = [];

  for (var i = 0; i < M; i++) {
    var _lines$pop$split3 = lines.pop().split(' '),
        _lines$pop$split4 = _slicedToArray(_lines$pop$split3, 2),
        P_i = _lines$pop$split4[0],
        Y_i = _lines$pop$split4[1];

    data.push([P_i, Y_i, i]);

    _P.push(P_i);
  }

  var P = _P.sort().filter(function (item, i) {
    return _P.indexOf(item) === i;
  });

  var sortedData = data.concat().sort(function (a, b) {
    return a[1] - b[1];
  });
  var result = [];

  var _loop = function _loop(_i2) {
    var IDs = sortedData.filter(function (_ref) {
      var _ref2 = _slicedToArray(_ref, 2),
          p = _ref2[0],
          _ = _ref2[1];

      return p == P[_i2];
    }).map(function (_ref3, x) {
      var _ref4 = _slicedToArray(_ref3, 3),
          P = _ref4[0],
          Y = _ref4[1],
          i = _ref4[2];

      return [Y, zerofill(P, 6) + zerofill(x + 1, 6), i];
    });
    var _iteratorNormalCompletion = true;
    var _didIteratorError = false;
    var _iteratorError = undefined;

    try {
      for (var _iterator = IDs[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
        var _step$value = _slicedToArray(_step.value, 3),
            Y = _step$value[0],
            id = _step$value[1],
            _i3 = _step$value[2];

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

  for (var _i2 = 0; _i2 < N; _i2++) {
    _loop(_i2);
  }

  console.log(result.join('\n'));
};

f1();