#include <iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
ll b[100000];
ll a[100000];
vector<ll>v[100000];
int main()
{
      ll n,m;
      cin>>n>>m;
       for(ll i=0;i<m;i++)
       {
           cin>>a[i]>>b[i];
           v[a[i]].push_back(b[i]);
       }
       for(ll i=1;i<=n;i++)
        sort(v[i].begin(),v[i].end());



    for(ll i=0;i<m;i++)
    {
        ll ans = lower_bound(v[a[i]].begin(),v[a[i]].end(),b[i]) - v[a[i]].begin();
        printf("%06lld%06lld\n",a[i],ans+1);
    }




    return 0;
}
