// Original C++ solution (slower):
#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long ll;

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

const int limit = 100000;

int N, M;

int P[limit], Y[limit];

vector<int> yd[limit + 1];

int main() {

    scanf("%d%d", &N, &M);

    rep(i, M) {

        scanf("%d%d", &P[i], &Y[i]);

        yd[P[i]].push_back(Y[i]);

    }

    rep(i, N) {

        sort(yd[i + 1].begin(), yd[i + 1].end()); //県ごとにyear並び替え

    }

    rep(i, M) {

        printf("%012lld\n", ll(P[i]) * limit * 10 + int(lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]) - yd[P[i]].begin()) + 1);

    }

    return 0;

}


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

using namespace std;

//type

typedef long long ll;

#define pii pair<int, int>

#define vi vector<int>

//x * y * 1.0 can cause overflow

//constant

#define inf (int)(1e9+7)

#define mod (ll)(1e9+7)

#define eps 1e-10

//omission

#define eb emplace_back

#define F first

#define S second

#define SZ(x) ((int)(x).size())

#define all(v) v.begin(), v.end()

#define ios cin.tie(0); ios::sync_with_stdio(false)

#define FIX(a) cout << fixed << setprecision(a)

//loop

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

#define rep3(i, st, n) for (int i = st; i < n; ++i)

//manip

#define chmax(a, b) a = max(a, b)

#define chmin(a, b) a = min(a, b)

#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());

#define fill(x, y) memset(x, y, sizeof(x))

#define ceil(a, b) a / b + !!(a % b)

template<class T> T power_mod(T a, T b) {return b ? power_mod(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}

template<class T> T power(T a, T b) {return b ? power(a * a, b / 2) * (b % 2 ? a : 1) : 1;}

#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())

#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())

template<typename T> T gcd(T a, T b) {if (b == 0) return a; return gcd(b, a % b);}

template<typename T> T lcm(T a, T b) {return a / gcd(max(a, b), min(a, b)) * b;} //先に割る!!

#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl

#define outaa(a, m, n) rep(i, m) {rep(j, n) cout << a[i][j] << " "; cout << endl;} cout << endl

#define out(a) cout << a << endl

#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl



//algorithm

//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0

//bfs, not x, y, i, j

//not !(i % 2), i % 2 == 0

//minimal required terms

//cast caution

//look constraints always

//nHk = n-1+kCn-1





bool comp(pair<int, pii> a, pair<int, pii> b) {

    if (a.S.F != b.S.F) return a.S.F < b.S.F;

    return a.S.S < b.S.S;

}

int main() {

    int n, m; cin >> n >> m;

    vector<int> p(m);

    vector<tuple<int, int, int> > v(m);

    rep(i, m) {

        cin >> p[i];

        int x; cin >> x;

        v[i] = make_tuple(p[i], x, i);

    }

    sort(all(v));

    

    vector<int> order(m);

    

    order[get<2>(v[0])] = 1;

    int cnt = 1;

    rep3(i, 1, m) {

        if (get<0>(v[i]) == get<0>(v[i - 1])) {

            cnt++;

            order[get<2>(v[i])] = cnt;

        } else {

            cnt = 1;

            order[get<2>(v[i])] = cnt;

        }

    }

    

    

    

    rep(i, m) {

        cout << setw(6) << setfill('0') << p[i];

        cout << setw(6) << setfill('0') << order[i] << endl;

        

    }

    

    

}


// Fastest known solution for this problem: