/*  /$$                                     /$$
      | $$                                    | $$
  /$$$$$$$  /$$$$$$   /$$$$$$$  /$$$$$$   /$$$$$$$  /$$$$$$   /$$$$$$
 /$$__  $$ /$$__  $$ /$$_____/ /$$__  $$ /$$__  $$ /$$__  $$ /$$__  $$
| $$  | $$| $$$$$$$$| $$      | $$  \ $$| $$  | $$| $$$$$$$$| $$  \__/
| $$  | $$| $$_____/| $$      | $$  | $$| $$  | $$| $$_____/| $$
|  $$$$$$$|  $$$$$$$|  $$$$$$$|  $$$$$$/|  $$$$$$$|  $$$$$$$| $$
 \_______/ \_______/ \_______/ \______/  \_______/ \_______/|__//$$$$$$ /$$$$$$
                                                               |______/|______/

*/
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <unordered_map>
#define fastio        ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ln            cout << endl;
#define vi            vector<int>
#define vll           vector<long long>
#define sortl(vec)    sort(vec.begin(), vec.end());
#define sortr(vec)    sort(vec.rbegin(), vec.rend());
#define forn(i, x, n) for(long long i = x; i < n; i++)
#define revn(i, n, x) for(long long i = n; i >= x; i--)
#define in(vec)       for(auto &it : vec) cin >> it;
#define	out(vec)      for(auto &it : vec) cout << it << " "; ln
#define ll            long long
#define pb            emplace_back
#define mp            make_pair
#define um            unordered_map
#define pii           pair<int, int>
#define pll           pair<ll, ll>
#define f             first
#define sec           second
#define pi            3.14159265359
#define o(x)		  cout << x << endl;
#define all(a)        a.begin(), a.end()
#define CLOCK         cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
using namespace std;

const ll Nfact = 200005;
const ll mod = 1000000007;
const ll Nseive = 1000005;
//https://codeforces.com/blog/entry/74640?#comment-587521

vector<bool> is_prime(Nseive, true);
void seive() {
	is_prime[0] = is_prime[1] = false;
	for (ll i = 2; i * i <= Nseive; i++) {
		if (is_prime[i]) {
			for (ll j = i * i; j <= Nseive; j += i)
				is_prime[j] = false;
		}
	}
}

ll bS(ll l, ll r, ll x, vll arr) {
	while (l <= r) {
		ll m = l + (r - l) / 2;

		if (arr[m] == x)
			return m;

		if (arr[m] < x)
			l = m + 1;

		else
			r = m - 1;
	}

	return -1;
}

void primeFactors(ll n) {
	while (n % 2 == 0) {
		//cout << 2 << " ";
		n = n / 2;
	}

	for (ll i = 3; i <= sqrt(n); i += 2) {
		while (n % i == 0) {
			//cout << i << " ";
			n = n / i;
		}
	}

	if (n > 2)
		cout << n << " ";
}

ll power(ll x, ll y, ll p) {
	ll res = 1;
	x = x % p;

	while (y > 0) {
		if (y & 1)
			res = (res * x) % p;

		y = y >> 1;
		x = (x * x) % p;
	}
	return res;
}

ll modulo(ll a, ll b) {
	ll c = a % b;
	return (c < 0) ? c + b : c;
}

//Use these functions below only when modulus is involved
ll mul(ll x, ll y) {
	return (x * y) % mod;
}

ll inv(ll x) {
	return power(x, mod - 2, mod);
}

ll divide(ll x, ll y)
{
	return mul(x, inv(y));
}

ll fact[Nfact];
void precalc() { // Call this once in main()
	fact[0] = 1;
	for (ll i = 1; i < Nfact; i++)
		fact[i] = mul(fact[i - 1], i);
}

ll nCr(ll n, ll k) {
	if (n < k)
		return 0;
	return divide(fact[n], mul(fact[k], fact[n - k]));
}

int main() {
// in(vec) works for size-defined type vectors

#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input1.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output1.txt", "w", stdout);
#endif

	fastio
	ll t = 1;
	while (t--) {
		ll n, m;
		cin >> n >> m;
		vector<vll>vec(n + 1);
		vector<pll>pairs(m);
		ll a, b;
		forn(i, 0, m) {
			cin >> a >> b;
			vec[a].pb(b);
			pairs[i].f = a;
			pairs[i].sec = b;
		}

		forn(i, 1, n + 1) {
			if (vec[i].size()) {
				//o(vec[i].size())
				sortl(vec[i])
			}
		}
		string str, le, de;
		map<pll, string>hash;

		forn(i, 1, n + 1) {
			forn(j, 0, vec[i].size()) {
				str = "";
				le = to_string(i);
				de = to_string(j + 1);
				str.append(6 - le.size(), '0');
				str += le;
				str.append(6 - de.size(), '0');
				str += de;
				hash[ {i, vec[i][j]}] = str;
				//o(str)
			}
		}

		forn(i, 0, m) {
			o(hash[pairs[i]])
		}

	}
	CLOCK
	return 0;
}



Measured memory_bytes: 19844