code

#include <bits/stdc++.h>
using namespace std;
struct x{
    long long si;
    long long id;
    int dr;
    long long sxid;
};
bool cmp(x a, x b){
    return a.si*1000000+a.id < b.si*1000000+b.id;
}
int main(){
    x f[100002];
    long long n, m, nid[100002] = {};
    cin >> n >> m;
    int pres, pred;
    for (int i = 0; i < m; i++){
        cin >> f[i].si >> f[i].id;
        f[i].dr = i;
    }
    sort(f, f + m, cmp);
    for (int i = 0; i < m; i++){
        if (i==0){
            pres = f[i].si;
            pred = f[i].id;
            f[i].sxid = 1;
        } else if (f[i].si != pres){
            f[i].sxid = 1;
        } else {
            if (i) f[i].sxid = f[i-1].sxid + 1;
        }
    }
    for(int i=0;i<m;i++)nid[f[i].dr]=f[i].si*1000000+f[i].sxid;
    for(int i=0;i<m;i++)printf("%012d\n",nid[i]);
    return 0;
}