// Slower C++ solution:
#include <iostream>

#include <string>

#include <string.h>

#include <algorithm>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <cmath>

#include <stdio.h>

#include <vector>

#include <time.h>



//     MLE,TLE魔

//↓↓↓↓↓↓↓↓↓↓↓↓

#define int long long

//↑↑↑↑↑↑↑↑↑↑↑↑

//     MLE,TLE魔

#define endre getchar();getchar();return 0

#define moder 1000000007

#define inf 1000000000000000000

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

#define REP(i,n) for(int i=1;i<n;i++)

#define P pair<int,int>

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

#define prique(T) priority_queue<T,vector<T>,greater<T>>

#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())

using namespace std;



bool prime(int n) {

	for (int i = 2; i <= sqrt(n); i++) {

		if (n%i == 0)return false;

	}

	return n != 1;

}

int gcd(int x, int y) {

	if (y == 0)return x;

	return gcd(y, x%y);

}

int lcm(int x, int y) {

	return x * y / gcd(x, y);

}

int mod_pow(int x, int y, int mod) {

	int res = 1;

	while (y > 0) {

		if (y & 1) {

			res = res * x%mod;

		}

		x = x * x%mod;

		y >>= 1;

	}

	return res;

}

int kai(int x) {

	if (x == 0)return 1;

	return (kai(x - 1)*x) % moder;

}

int comb(int x, int y) {

	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;

}

struct edge { int to, cost; };

int dx[5] = { 0,1,0,-1 }, dy[5] = { 1,0,-1,0 };

map<int, int>factor(int x) {

	map<int, int>res;

	for (int i = 2; i*i <= x; i++) {

		while (x%i == 0) {

			x /= i;

			res[i]++;

		}

	}

	if (x != 1)res[x]++;

	return res;

}

/*--------Library Zone!--------*/



int n, m;

int a[100005], b[100005];

vector<int>vec[100005];

signed main() {

	cin >> n >> m;

	rep(i, m) {

		cin >> a[i] >> b[i];

		vec[a[i]].push_back(b[i]);

	}

	rep(i, n + 1)sort(all(vec[i]));

	rep(i, m) {

		int si = to_string(a[i]).size();

		for (int j = si; j < 6; j++)cout << 0;

		cout << a[i];

		int me = lower_bound(all(vec[a[i]]), b[i]) - vec[a[i]].begin() + 1;

		si = to_string(me).size();

		for (int j = si; j < 6; j++)cout << 0;

		cout << me << endl;

	}

	endre;

}

// Faster C++ solution for the same problem (measured speedup: 3.514447598999734x):
#include <bits/stdc++.h>

#define int long long

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

#define inf (int)(3e18+7)

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

#define REP(i,n) for(int i=1;i<n;i++)

#define P pair<int,int>

#define PiP pair<int,pair<int,int>>

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

#define mkp make_pair

#define mkt make_tuple

#define prique(T) priority_queue<T,vector<T>,greater<T>>

#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())

using namespace std;



bool prime(int x) {

	for (int i = 2; i * i <= x; i++) {

		if (x % i == 0)return false;

	}

	return x > 1;

}

int gcd(int x, int y) {

	if (y == 0)return x;

	return gcd(y, x % y);

}

int lcm(int x, int y) {

	return x / gcd(x, y) * y;

}

int kai(int x, int y) {

	int res = 1;

	for (int i = x - y + 1; i <= x; i++) {

		res *= i; res %= mod;

	}

	return res;

}

int mod_pow(int x, int y) {

	int res = 1;

	while (y > 0) {

		if (y & 1) {

			res = res * x % mod;

		}

		x = x * x % mod;

		y >>= 1;

	}

	return res;

}

int comb(int x, int y) {

	if (y > x)return 0;

	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;

}

/*--------Library Zone!--------*/



int n, m;

int a[114514], b[114514];

pair<P,int>p[114514];

int num[114514];

string mystoi(int x) {

	string res = to_string(x);

	while (res.size() < 6) {

		res = "0" + res;

	}

	return res;

}

signed main() {

	cin >> n >> m;

	rep(i, m) {

		cin >> a[i] >> b[i];

		p[i] = { {a[i],b[i]},i };

	}

	sort(p, p + m);

	int index = 1;

	rep(i, m) {

		num[p[i].second] = index;

		index++;

		if (p[i].first.first != p[i + 1].first.first)index = 1;

	}

	rep(i, m) {

		cout << mystoi(a[i]) << mystoi(num[i]) << endl;

	}

}