// Original C++ solution (slower):
#include <bits/stdc++.h>

#define rep(i, m, n) for(int i = m; i < (n); i++)

#define print(x) cout << (x) << endl;

#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;

#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}

#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;

#define INF (1e18)

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

typedef struct{

    int x;

    int y;

} P;

typedef struct{

    ll to;

    ll cost;

} edge;

typedef pair<ll, ll> lpair;

bool comp(pair<lpair, ll> p1, pair<lpair, ll> p2){

    if(p1.first.first == p2.first.first){

        return (p1.first.second < p2.first.second);

    }

    return p1.first.first < p2.first.first;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N,M;

    ll P[100010], Y[100010];

    cin >> N >> M;

    rep(i,0,M){

        cin >> P[i] >> Y[i];

    }

    vector< pair<lpair, ll> > lp;

    rep(i,0,M){

        lp.push_back(make_pair(make_pair(P[i], Y[i]), i));

    }

    sort(lp.begin(), lp.end(), comp);

    vector< pair<string, string> > ans(100010);

    ll rank = 0;

    ll prev_pref = lp[0].first.first;

    rep(i,0,M){

        ll n = lp[i].second;

        ll pre_num = lp[i].first.first;

        if(pre_num == prev_pref){

            rank++;

        }else{

            rank = 1;

        }

        prev_pref = pre_num;

        ll keta = to_string(pre_num).size();

        ll zero_num = 6 - keta;

        ans[n].first = string(zero_num, '0') + to_string(pre_num);

        ll keta2 = to_string(rank).size();

        ll zero_num2 = 6 - keta2;

        ans[n].second = string(zero_num2, '0') + to_string(rank);

    }

    rep(i,0,M){

        cout << ans[i].first << ans[i].second << endl;

    }

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define rep(i, m, n) for(int i = m; i < (n); i++)

#define print(x) cout << (x) << endl;

#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;

#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}

#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;

#define INF (1e18)

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

typedef struct{

    int x;

    int y;

} P;

typedef struct{

    ll to;

    ll cost;

} edge;

typedef pair<ll, ll> lpair;

bool comp(pair<lpair, ll> p1, pair<lpair, ll> p2){

    if(p1.first.first == p2.first.first){

        return (p1.first.second < p2.first.second);

    }

    return p1.first.first < p2.first.first;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N,M;

    ll P[100010], Y[100010];

    cin >> N >> M;

    rep(i,0,M){

        cin >> P[i] >> Y[i];

    }

    vector< pair<lpair, ll> > lp;

    rep(i,0,M){

        lp.push_back(make_pair(make_pair(P[i], Y[i]), i));

    }

    sort(lp.begin(), lp.end(), comp);

    vector<lpair> ans(100010);

    ll rank = 1;

    rep(i,0,M){

        ll n = lp[i].second;

        ll pre_num = lp[i].first.first;

        if(i != 0){

            if(pre_num == lp[i-1].first.first){

                rank++;

            }else{

                rank = 1;

            }

        }

        ans[n].first = pre_num;

        ans[n].second = rank;

    }

    rep(i,0,M){

        cout << setfill('0') << right << setw(6) << ans[i].first;

        cout << setfill('0') << right << setw(6) << ans[i].second << endl;

    }



    // vector< pair<string, string> > ans(100010);

    // ll rank = 0;

    // ll prev_pref = lp[0].first.first;

    // rep(i,0,M){

    //     ll n = lp[i].second;

    //     ll pre_num = lp[i].first.first;

    //     if(pre_num == prev_pref){

    //         rank++;

    //     }else{

    //         rank = 1;

    //     }

    //     prev_pref = pre_num;

    //     ll keta = to_string(pre_num).size();

    //     ll zero_num = 6 - keta;

    //     ans[n].first = string(zero_num, '0') + to_string(pre_num);

    //     ll keta2 = to_string(rank).size();

    //     ll zero_num2 = 6 - keta2;

    //     ans[n].second = string(zero_num2, '0') + to_string(rank);

    // }

    // rep(i,0,M){

    //     cout << ans[i].first << ans[i].second << endl;

    // }

}


// Fastest known solution for this problem: