#include <bits/stdc++.h>
//#include <mylib.h>
using namespace std;
//cin.sync_with_stdio(false);

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FOR_EQ(i,a,b) for(int i = (a); i <= (b); ++i)
#define FOR_RE(i,a,b) for(int i = (a); i > (b); --i)
#define rep(i,n) FOR(i,0,n)
#define rep_eq(i,n) FOR_EQ(i,0,n)
#define rep_re(i,n) FOR_RE(i,n,0)

#define DEBUG_VARIABLE(variable) cout << #variable << ":" << variable << endl

#define WHITE 1//（未訪問）
#define GRAY 2//（訪問）未だに訪問していない頂点への辺を持っている。スタックに退避。
#define BLACK 3//（訪問完了）未訪問への頂点への辺を持たない
#define N 100
#define INFTY (1 << 21) //10^21
#define INF (1 << 9)
int M[N][N];//隣接行列
int color[N];

//1個上から時計周り
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//上右下左
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {-1, 0, 1, 0};
static const int NIL = -1;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> Vector;
typedef vector<Vector>	DVector;
int n;

void printArray(int *array, int);
void printVector(Vector &v);
void printDimention(DVector &dv);
//nCr方式で組み合わせの数を求める
int combination(int, int);
//nPrで階乗を求める
int factorial(int, int);
//桁数を返す
int find_digits(int);
// 各桁の和を計算する関数
int findSumOfDigits(int);
//次数を得る
int degree(int);
//四捨五入
int shishagonyu(double);
//切り上げ
int roundUp(double);
//切り捨て
int roundDown(double);
//四捨五入
int roundOff(double);
//最大公約数(Greatest Common Divisor)
int gcd (int, int);
//最小公倍数(Least Common Multiple)
int lcm(int, int);
//素因数分解
void prime_factorization(int);
//エラトステネスの篩
int Eratosthenes(int);
//偶奇判定。奇数ならtrue。
bool odd_even(int);
/*
typedef struct _city{
    int id;
    int pref;
    int year;
    int order;
}City;
*/
typedef pair<int, int> year_order;
typedef pair<int, year_order> pref_attri;
typedef pair<int, pref_attri> id_attri;
typedef id_attri City;  //番号，県，年，県ごとの番号
int id_attri::* id = &id_attri::first;
pref_attri id_attri::* attri1 = &id_attri::second;
int pref_attri::* pref = &pref_attri::first;
year_order pref_attri::* attri2 = &pref_attri::second;
int year_order::* year = &year_order::first;
int year_order::* order = &year_order::second;

bool comp1(City l, City r){
    if(l.*attri1.*pref != r.*attri1.*pref)
        return l.*attri1.*pref < r.*attri1.*pref;
    if(l.*attri1.*attri2.*year != r.*attri1.*attri2.*year)
        return l.*attri1.*attri2.*year < r.*attri1.*attri2.*year;
    return l.*id < r.*id;
}

bool comp2(City l, City r){
    return l.*id < r.*id;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int m;
    cin >> n >> m;
    vector<City> city(m);
    rep(i, m){
        city[i].*id = i;
        cin >> city[i].*attri1.*pref >> city[i].*attri1.*attri2.*year;
    }
    sort(city.begin(), city.end(), comp1);
    int cnt = 1;
    rep(i, m){
        if(i == 0){
            city[i].*attri1.*attri2.*order = cnt;
            cnt++;
            continue;
        }
        if(city[i - 1].*attri1.*pref == city[i].*attri1.*pref){
            city[i].*attri1.*attri2.*order = cnt;
            cnt++;
        }else{
            cnt = 1;
            city[i].*attri1.*attri2.*order = cnt;
            cnt++;
        }
    }
    sort(city.begin(), city.end(), comp2);
    rep(i, m){
        printf("%06d", city[i].*attri1.*pref);
        printf("%06d\n", city[i].*attri1.*attri2.*order);
    }
}

//配列の表示
void printArray(int array[], int n){
    rep(i, n){
        if(i)   cout << " ";
        cout << array[i];
    }
    cout << endl;
}

//Vectorの表示
void printVector(Vector &v){
    rep(i, (int)v.size()){
        if(i)   cout << " ";
        cout << v[i];
    }
    cout << endl;
}

//二次元配列の表示
void printDimention(DVector &dv){
    rep(i, (int)dv.size()){
        rep(j, (int)dv[i].size()){
            if(j)   cout << " ";
            cout << dv[i][j];
        }
        cout << endl;
    }
}

//numの中に何個2がかかってるか
int factor2(int num){
    int cnt = 0;
    while(num % 2 == 0){
        num /= 2;
        cnt++;
    }
    return cnt;
}

//nCr方式で組み合わせの数を求める
int combination(int n, int r){
    int up = 1, down = 1;

    rep(i, n)   up *= (i + 1);

    rep(i, n-r) down *= (i + 1);
    rep(i, r)   down *= (i + 1);

    return up/down;
}

//nPr方式で階乗を求める
int factorial(int n, int r){
    if(n < r){
        cout << "error" << endl;
        return 0;
    }else{
        int res = 1;
        while(r){
            r--;
            res *= n;
            n--;
        }
        return res;
    }
}

//桁数を返す
int find_digits(int n){
    int digit = 0;

    while(n){
        n /= 10;
        digit++;
    }
    return digit;
}
// 各桁の和を計算する関数
int findSumOfDigits(int n){
    int sum = 0;
    while (n > 0) { // n が 0 になるまで
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
//次数を得る
int degree(int n){
    int count = 0;
    while(1){
        if(count <= 0)  break;
        count /= 2;
        count++;
    }
    return count;
}

//四捨五入
int shishagonyu( double x )
{
    return (int)( x < 0.0 ? x-0.5 : x+0.5 );
}

//切り上げ
int roundUp(double n){
    if(n >= 0){ 
        return (int)n + 1;
    }else{
        return (int)n - 1;
    }
}

//切り捨て
int roundDown(double n){
    return (int)n;
}

//四捨五入
int roundOff(double n){
    double decimal = 0;

    decimal = n - (int)n;

    if(decimal >= 0.5 || decimal <= -0.5){
        return roundUp(n);
    }else{
        return roundDown(n);
    }
}

//最大公約数(Greatest Common Divisor)
int gcd (int m, int n){
    //引数に0がある場合は0を返す
    if(m == 0 || n == 0)    return 0;
    
    //ユークリッドの互除法
    while(m != n){
        if(m > n)   m = m - n;
        else    n = n - m;
    }
    return m;
}

//最小公倍数(Least Common Multiple)
int lcm(int m, int n){
    //引数に0がある場合は0を返す
    if(m == 0 || n == 0)    return 0;
    
    //lcm = m * n / gcd(m, n)
    return ((m / gcd(m, n)) * n);
}

//素因数分解
void prime_factorization(int n){
    int a = 2, res;
    
    while(n >= a * a){
        if(n % a == 0){
            res = a;
            //resをグローバルな配列に代入すれば記録できる。
            n /= a;
        }else{
            a++;
        }
    }
    //ラス1の素因数
    res = n;
}

//エラトステネスの篩
int Eratosthenes(int n){
    bool prime[n];
    //prime[0]が1、prime[n - 1]がn。
    rep(i, n)   prime[i] = true;
    
    for(int i = 2; i < sqrt(n); i++){
        if(prime[i]){
            for(int j = 0; i * (j + 2) < n; j++){
                prime[i *(j + 2)] = false;
            }
        }
    }

    int cnt = 0;
    for(int i = 2; i < n; i++){
        if(prime[i]){
            cnt++;
        }
    }
    return cnt;
}
//偶奇判定。奇数ならtrue。
bool odd_even(int num){
    bool judge;
    if(num % 2){
        judge = true;
    }else{
        judge = false;
    }
    return judge;
}

Measured memory_bytes: 3072