const zeroPadding = (num, length) => {
  return ('0000000000' + num).slice(-length);
};

const Main = (input) => {
  // 入力値の整形
  input = input.split('\n');
  input.shift();
  const cities = input
    .map((line, index) => {
      // 空行は処理をスキップ
      if (line.length === 0) return null;
      const lineArray = line.split(' ');
      const ken = lineArray[0];
      const year = lineArray[1];
      return {
        index: index,
        ken: ken,
        year: year,
      };
    })
    .filter((data) => {
      // null値の除外
      return data;
    });

  const kenArray = [];
  cities
    .concat()
    .sort((a, b) => {
      return a.year - b.year;
    })
    .forEach((city) => {
      if (!kenArray[city.ken]) kenArray[city.ken] = [];
      kenArray[city.ken].push(city);
      cities[city.index].cityId =
        zeroPadding(city.ken, 6) + zeroPadding(kenArray[city.ken].length, 6);
    });

  cities.forEach((city) => {
    console.log(city.cityId);
  });
};

//* この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));
