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

int main(){
    int n,m;
    cin>>n>>m;
    int p[100000],y[100000];
    vector<int> v[100001];
    for(int i=0;i<m;i++){
        cin>>p[i]>>y[i];
        v[p[i]].push_back(y[i]);
    }
    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end());
    }
    for(int i=0;i<m;i++){
        cout<<setfill('0')<<setw(6)<<p[i];
        cout<<setfill('0')<<setw(6);
        cout<<lower_bound(v[p[i]].begin(),v[p[i]].end(),y[i])-v[p[i]].begin()+1<<endl;
    }
}
