#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define ALL(obj) (obj).begin(),(obj).end()

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

vector<int> dy = { 0,0,1,-1 };
vector<int> dx = { 1,-1,0,0 };

template<class T> void corner(bool flg, T hoge) {
	if (flg) {
		cout << hoge << endl;
		exit(0);
	}
	else return;
}

template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {
	o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;
}

template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {
	o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;
}

template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {
	o << "{" << obj.first << ", " << obj.second << "}"; return o;
}

template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

void print(void) {
	cout << endl;
}

template <class Head> void print(Head&& head) {
	cout << head;
	print();
}

template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {
	cout << head << " ";
	print(forward<Tail>(tail)...);
}

void YN(bool flg) {
	cout << ((flg) ? "YES" : "NO") << endl;
}

void Yn(bool flg) {
	cout << ((flg) ? "Yes" : "No") << endl;
}

void yn(bool flg) {
	cout << ((flg) ? "yes" : "no") << endl;
}

//Binary Indexed Tree
class Binary_Indexed_Tree_Range_Sum_Query {
public:
	int N;
	vector<long long> node;

	Binary_Indexed_Tree_Range_Sum_Query(int N) : N(N), node(vector<long long>(N + 1, 0)) {
	}

	void update(int idx, long long var) {
		for (++idx; idx <= N; idx += idx & -idx) node[idx] += var;
	}

	long long getvar(int idx) {
		long long ret = 0;
		for (++idx; idx >= 1; idx -= idx & -idx) ret += node[idx];
		return ret;
	}
};

//Seat Pressure
class Zarts {
public:
	vector<long long> solve(const vector<long long> & ar,int cnt = 0) {
		vector<long long> ret;
		map<long long, int> mp;
		for (auto val : ar) mp[val] = 0;
		for (auto &u : mp) u.second = cnt++;
		for (auto val : ar) ret.push_back(mp[val]);
		return ret;
	}
};

string zero(int n) {
	string S="";
	int m = n;
	int k = 6;
	for (; m > 0; m /= 10) k--;
	for (int i = 0; i < k; ++i) S.push_back('0');
	S = S + to_string(n);
	return S;
}

int main() {
	int N, M; cin >> N >> M;
	V<int> P(M), Y(M);
	V<string> ans(M);
	map<int, pair<int,int>> mp;
	REP(i, M) cin >> P[i] >> Y[i];
	REP(i, M) mp[Y[i]] = {P[i],i};
	V<V<int>> ord(N+1);
	REP(i, M) ord[P[i]].push_back(Y[i]);
	REP(i, N+1) {
		sort(ALL(ord[i]));
		REP(j, ord[i].size()) {
			int y = ord[i][j];
			int c = mp[y].first;
			int idx = mp[y].second;
			ans[idx] = zero(c) + zero(j + 1);
		}
	}
	REP(i, M) cout << ans[i] << endl;
	
	return 0;
}



Measured memory_bytes: 21120