#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    /*int x,y;cin>>x>>y;
    cout<<x+(y/2)<<endl;*/

    /*int n; cin>>n;
    double t,a; cin>>t>>a;
    double mi=INF;
    int idx;
    for(int i=0;i<n;i++){
        int h;cin>>h;
        if(abs(a-(t-0.006*h))<mi){
            mi=abs(a-(t-0.006*h));
            idx=i+1;
        }
    }
    cout<<idx<<endl;*/

    int n,m;cin>>n>>m;
    vector<vector<P>> ids(n+1); // (year, idx)
    vector<string> res(m+1);
    for(int i=0;i<m;i++){
        int p,y;cin>>p>>y;
        ids[p].push_back(P(y,i+1));
    }
    for(int i=1;i<=n;i++){
        sort(ids[i].begin(),ids[i].end());
        for(int j=0;j<(int)ids[i].size();j++){
            int p=i, x = j+1, idx=ids[i][j].second;
            string s="", ps=to_string(p), xs=to_string(x);
            for(int k=0;k<6-(int)ps.length();k++) s+="0";
            s+=ps;
            for(int k=0;k<6-(int)xs.length();k++) s+="0";
            s+=xs;
            res[idx] = s;
        }
    }
    for(int i=1;i<=m;i++) cout<<res[i]<<endl;

    /*int H, W, K;
    cin >> H >> W >> K;
    if (W == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    vector<vector<ll>> dp(H + 2, vector<ll>(W + 1, 0));
    vector<bool> v(1 << W, true);
    for (int i = 0; i < (1 << (W - 1)); i++)
    {
        for (int j = 0; j < W - 2; j++)
        {
            if (((i >> j) & 1) && ((i >> (j + 1)) & 1))
            {
                v[i] = false;
            }
        }
    }
    // dp[i][j] := 高さ i の時 j にいるような valid なあみだの数
    dp[1][0] = 1;
    for (int i = 1; i <= H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            for (int k = 0; k < (1 << (W - 1)); k++)
            {
                if (!v[k])
                    continue;
                if (j == 0)
                {
                    if (k & 1)
                    {
                        dp[i + 1][j + 1] += dp[i][j];
                        dp[i + 1][j + 1] %= MOD;
                    }
                    else
                    {
                        dp[i + 1][j] += dp[i][j];
                        dp[i + 1][j] %= MOD;
                    }
                }
                else if (j == W - 1)
                {
                    if ((k >> (j - 1)) & 1)
                    {
                        dp[i + 1][j - 1] += dp[i][j];
                        dp[i + 1][j - 1] %= MOD;
                    }
                    else
                    {
                        dp[i + 1][j] += dp[i][j];
                        dp[i + 1][j] %= MOD;
                    }
                }
                else
                {
                    if ((k >> (j - 1)) & 1)
                    {
                        dp[i + 1][j - 1] += dp[i][j];
                        dp[i + 1][j - 1] %= MOD;
                    }
                    else if ((k >> j) & 1)
                    {
                        dp[i + 1][j + 1] += dp[i][j];
                        dp[i + 1][j + 1] %= MOD;
                    }
                    else
                    {
                        dp[i + 1][j] += dp[i][j];
                        dp[i + 1][j] %= MOD;
                    }
                }
            }
        }
    }
    cout << dp[H + 1][K - 1] << endl;
    */
}


Measured memory_bytes: 12416