#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll n,m;
    cin>>n>>m;
    vector<pair<ll,ll> >pr(m);
    map<ll,pair<ll,ll> >mp;
    vector<ll>v(m);
    for(ll i=0;i<m;++i)
    {
        cin>>pr[i].first>>pr[i].second;
        v[i] = pr[i].second;
    }
    sort(pr.begin(),pr.end());
    ll c=1;

    for(ll i=0;i<m;++i)
    {
        mp.insert({pr[i].second,{pr[i].first,c}});
        ++c;
    if(pr[i].first!=pr[i+1].first)
            c = 1;
    }

    for(ll i=0;i<m;++i)
    {
        printf("%.6lld%.6lld\n",mp[v[i]].first,mp[v[i]].second);
    }
}
