#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int INF = 1e9;
const int mod = 1e9+7;

int main()
{
    int n,m;
    cin >> n >> m;
    vector<int> p(m),y(m),z[n];
    for(int i = 0; i < m; i++){
        cin >> p[i] >> y[i];
        z[p[i]-1].push_back(y[i]);
    }

    for(int i = 0; i < n; i++) sort(z[i].begin(),z[i].end());

    for(int i = 0; i < m; i++){
        printf("%06d%06d\n",p[i],lower_bound(z[p[i]-1].begin(),z[p[i]-1].end(),y[i])-z[p[i]-1].begin()+1);
    }

    return 0;
}