#include <bits/stdc++.h>
using namespace std;
const long long int MAX = 100000;
const long long int MAX2 = 1000000000;
long long int M = MAX;
vector<long long int> P(M);
vector<long long int> Y(M);
vector<pair<long long int, long long int>> S(M);
int keta(int x) {
  int ans = 0;
  for (int i = 1; i < x; i++) {
    if (x % 10 * i == x) {
      return i;
      break;
    }
  }
}
int solve(int a) {
  if (a == 0) {
    return 1;
  } else if (S.at(a).first == S.at(a - 1).first) {
    return solve(a - 1) + 1;
  } else {
    return 1;
  }
}
int main() {
  long long int N;
  cin >> N >> M;
  for (long long int i = 0; i < M; i++) {
    cin >> P[i] >> Y[i];
    S.at(i).first = P[i];
    S.at(i).second = Y[i];
  }
  sort(S.begin(), S.end());
  vector<int> date(M);
  for (int i = 0; i < M; i++) {
    date[i] = solve(i);
  }
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      if (S.at(j).second == Y[i]) {
        for (int k = 0; k < 6 - keta(P[i]); k++) {
          cout << 0;
        }
        cout << P[i];
        for (int l = 0; l < 6 - keta(solve(j)); l++) {
          cout << 0;
        }
        cout << solve(j) << endl;
      }
    }
  }
}
