#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
using namespace std;

struct A
{
    long long ct;
    long long num;
    long long id;
} a[200000];

bool cmp(A a,A b)
{
    if(a.ct==b.ct)
        return a.num<b.num;
    return a.ct<b.ct;
}

long long b[200000],d[200000],c[200000];

int main()
{
    long long n,m;
    long long i,j;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        for(i=0; i<m; i++)
        {
            scanf("%lld%lld",&a[i].ct,&a[i].num);
            b[i]=a[i].ct;
            d[i]=a[i].num;
        }
        sort(a,a+m,cmp);
        for(j=0; j<m; j++)
        {
            for(i=1; i<=n; i++)
            {
                if(a[j].ct==i)
                {
                    a[j].id=1+c[i];
                    c[i]++;
                }
            }
        }
        for(i=0; i<m; i++)
            for(j=0; j<m; j++)
                if(b[i]==a[j].ct&&d[i]==a[j].num)
                {
                    printf("%06lld%06lld\n",a[j].ct,a[j].id);
                    a[j].ct=0;
                }

    }
    return 0;
}
