#define _GLIBCXX_DEBUG
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
using namespace std;

//struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

#define mp make_pair
#define pb push_back
#define FI first
#define SE second
#define INF (1 << 30)
#define FOR(i,a,b) for(int (i)=((int)a); (i)<((int)b); (i)++) // [a,b)
#define REP(i,N) FOR((i), 0, ((int)N)) // [0,N)
#define _overload9(_1,_2,_3,_4,_5,_6,_7,_8,_9,NAME,...) NAME
#define icin1(_1) int _1; cin >> _1
#define icin2(_2, ...) int _2; cin >> _2; icin1(__VA_ARGS__)
#define icin3(_3, ...) int _3; cin >> _3; icin2(__VA_ARGS__)
#define icin4(_4, ...) int _4; cin >> _4; icin3(__VA_ARGS__)
#define icin5(_5, ...) int _5; cin >> _5; icin4(__VA_ARGS__)
#define icin6(_6, ...) int _6; cin >> _6; icin5(__VA_ARGS__)
#define icin7(_7, ...) int _7; cin >> _7; icin6(__VA_ARGS__)
#define icin8(_8, ...) int _8; cin >> _8; icin7(__VA_ARGS__)
#define icin9(_9, ...) int _9; cin >> _9; icin8(__VA_ARGS__)
#define icin(...) _overload9(__VA_ARGS__,icin9,icin8,icin7,icin6,icin5,icin4,icin3,icin2,icin1)(__VA_ARGS__)
#define lcin(x) ll x; cin >> x
#define dcin(x) double x; cin >> x
#define scin(s) string s; cin >> s
#define aout1(_1) _1 << '\n'
#define aout2(_2, ...) _2 << ' ' << aout1(__VA_ARGS__)
#define aout3(_3, ...) _3 << ' ' << aout2(__VA_ARGS__)
#define aout4(_4, ...) _4 << ' ' << aout3(__VA_ARGS__)
#define aout5(_5, ...) _5 << ' ' << aout4(__VA_ARGS__)
#define aout6(_6, ...) _6 << ' ' << aout5(__VA_ARGS__)
#define aout7(_7, ...) _7 << ' ' << aout6(__VA_ARGS__)
#define aout8(_8, ...) _8 << ' ' << aout7(__VA_ARGS__)
#define aout9(_9, ...) _9 << ' ' << aout8(__VA_ARGS__)
#define aout(...) cout << _overload9(__VA_ARGS__,aout9,aout8,aout7,aout6,aout5,aout4,aout3,aout2,aout1)(__VA_ARGS__)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vcin(v,N) vi v(N); REP(i,N) cin >> v[i]
#define vcinl(v,N) vl v(N); REP(i,N) cin >> v[i]
#define vmax(v) *max_element(all(v)) // 遅い？いつか書き直す
#define vmin(v) *min_element(all(v))
#define vidx(v,it) distance((v).begin(),(it))
#define vsum(v) accumulate(all(v),0)
#define vsumr(v,a,b) accumulate((v).begin()+(a),(v).begin()+(b),0) //[a,b)
#define vfnd(v,val) find(all(v),val) // itrを返す。存在しない場合v.end()を返す
#define vcnt(v,val) count(all(v),val)
#define vrep(v,it) for(auto it=(v).begin(); it != (v).end(); ++it)

// デバッグ用
// dbg(...) printfと同様に使用可能 
// trc(var) (変数名)=(値)と表示
// stopif(val) 条件分が真の時に止まる
// vdbg(v) vの中身を表示
#ifdef LOCAL
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
    #define trc(var) cout << #var << "=" << var << endl
    #define trc2(v) cout << #v << "={"
    #define stopif(val) assert( !(val) )
    #define vdbg(v) vector_debug(v)
#else
    #define dbg(...) 1
    #define trc(var) 1
    #define trc2(v) 1
    #define stopif(val) 1
    #define vdbg(v) 1
#endif

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > vvi;
int gcd(int a, int b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);}
ll gcd(ll a, ll b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);}
template<typename C> inline void vector_debug(vector<C> v){trc2(v);ostream_iterator<C> o(cout,",");copy(all(v),o);cout<<"}"<<endl;}
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y,true) : false;}
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y,true) : false;}

// icin(x)    int x; cin >> x;   xは可変長引数
// aout(x)    cout << x << '/n'; xは可変長引数 
// vcin(A,N)  vi Aを宣言してcinで初期化
typedef struct{
    int P;
    int Y;
    int I;
    int NUM;
} city;

bool comp_y(const city &a,const city &b){
    return (a.P == b.P) ? a.Y < b.Y : a.P < b.P;
}
bool comp_i(const city &a,const city &b){
    return a.I < b.I;
}

int main(){
    icin(N,M);
    vector<city> v(M);
    REP(i,M){
        cin >> v[i].P >> v[i].Y;
        v[i].I = i;
    }
    sort(all(v),comp_y);
    int idx = 1;
    REP(i,M){
        if(i == 0){
            v[i].NUM = 1;
            idx++;
        }
        else{
            if(v[i].P == v[i-1].P){
                v[i].NUM = idx;
                idx++;
            }
            else{
                v[i].NUM = 1;
                idx = 2;
            }
        }
    }
    sort(all(v),comp_i);
    REP(i,M){
        printf("%06d%06d\n",v[i].P,v[i].NUM);
    }
    return 0;
}

Measured memory_bytes: 3072