/***"In the name of Allah(swt), the most gracious, most merciful. Allah(swt) blesses with knowledge whom he wants."***/
/*** "ALHAMDULILLAH for Everything..." ***/
#include<bits/stdc++.h>
using namespace std;
#define  fastt       ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define  ll         long long
#define  debug      printf("Come here!")
#define  inf        1000000000000000000
#define  pb         push_back
#define  mp         make_pair
#define  sz(a)      a.size()
#define  mem(a,b)   memset(a,b,sizeof(a))
#define  clr(x)     x.clear()
#define  ff         first
#define  ss         second
#define  case(x)    cout << "Case " << x <<": "

#define  md         1000000007
#define  pi         acos(-1.0)
#define  cos(a)     cos(a*pi/180)
#define  sin(a)     sin(a*pi/180)
#define  tan(a)     tan(a*pi/180)
#define  cosi(a)    acos(a)/(pi/180)
#define  sini(a)    asin(a)/(pi/180)
#define  tani(a)    atan(a)/(pi/180)

#define  vl         vector <ll>
#define  vs         vector <string>
#define  vc         vector <char>
#define  vpll       vector < pair <ll, ll> >
#define  vpsl       vector < pair <string, ll> >
#define  vpls       vector < pair <ll, string> >
#define  pql        priority_queue<ll>
#define  minpql     priority_queue<ll,vector<ll>,greater<ll> >

#define  setbits(x)     __builtin_popcountll(x)
#define  zerobits(x)    __builtin_ctzll(x)

#define toll(a) atoll(a.c_str())
string tostr(ll a) {stringstream rr;rr<<a;return rr.str();}
ll pow(ll c,ll d){return d==0?:c*pow(c,d-1);}
ll gcd(ll a,ll b) {return b==0? a:gcd(b,a%b);}
ll lcm(ll a,ll b) {return ((a*b)/gcd(a,b));}

/* mpp.max_load_factor(0.25); mpp.reserve(1024); */
/* cout << fixed << setprecision(12);*/

int main()
{
    fastt;
    ll n, z, m, k, i, j, x, y, p=0, h, f=0;
    cin>>n>>m;
    string s, s1, s2;
    ll a[m], b[m];
    vpll v;
    map<pair<ll, ll>, ll>mpp;
    for(i=0; i<m; i++){
        cin>>a[i]>>b[i];
        v.pb(mp(a[i], b[i]));
    }
    sort(v.begin(), v.end());
    x=v[0].ff;
    y=v[0].ss;
    h=x;
    k=0;
    mpp[{x, y}]=++k;
    for(i=1; i<v.size(); i++){
        x=v[i].ff;
        y=v[i].ss;
        if(x==h){
            mpp[{x, y}]=++k;
        }
        else{
            h=x;
            k=0;
            mpp[{x, y}]=++k;
        }
    }
    for(i=0; i<m; i++){
        x=a[i];
        y=b[i];
        z=mpp[{x, y}];
        s1=to_string(x);
        if(s1.size()==1){
            s="00000";
            s+=s1;
        }
        else if(s1.size()==2){
            s="0000";
            s+=s1;
        }
        else if(s1.size()==3){
            s="000";
            s+=s1;
        }
        else if(s1.size()==4){
            s="00";
            s+=s1;
        }
        else if(s1.size()==5){
            s="0";
            s+=s1;
        }
        else{
            s=s1;
        }
        s1=to_string(z);
        if(s1.size()==1){
            s+="00000";
            s+=s1;
        }
        else if(s1.size()==2){
            s+="0000";
            s+=s1;
        }
        else if(s1.size()==3){
            s+="000";
            s+=s1;
        }
        else if(s1.size()==4){
            s+="00";
            s+=s1;
        }
        else if(s1.size()==5){
            s+="0";
            s+=s1;
        }
        else{
            s+=s1;
        }
        cout<<s<<endl;
    }
    return 0;
}



Measured memory_bytes: 12676