#include<algorithm>
#include<iomanip>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<vector>
#include<bitset>
#include<cmath>
#define FOR(i,a,b) for(int i=(a); i<int(b); ++i)
#define RFOR(i,a,b) for(int i=(b)-1; i>=int(a); --i)
#define rep(i,n) FOR(i,0,n)
#define rep1(i,n) FOR(i,1,int(n)+1)
#define rrep(i, n) RFOR(i, 0, n)
#define rrep1(i, n) RFOR(i, 1, int(n) + 1)
#define all(c) begin(c), end(c)
#define al(d) d.begin(),d.end()
#define fill(n) std::setfill('0')<<std::right<<std::setw(n)
template <typename T>
using vec = std::vector<T>;
using vi = vec<int>;
using vvi = vec<vi>;
using pii = std::pair<int, int>;
using ll = long long;
using ld = long double;
using namespace std;
const int MOD = 1000000007;

template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}
template <class T>
vector<T> getv(int n){
	vector<T> vec;
	rep(i,n){
		T input;
		cin >> input;
		vec.emplace_back(input);
	}
	return vec;
}

using AdjList = vector<vector<int>>;
using Weight = int;
using Flow = int;
struct Edge {
	int src, dst;
	Weight weight;
	Flow cap;
	Edge() : src(0), dst(0), weight(0) {}
	Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;
void add_edge(Graph &g, int a, int b, Weight w = 1) {
	g[a].emplace_back(a, b, w);
	g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }
// Recieve edge(=(int,int)) as an adj list.
AdjList getadj(int N, int M){
	// Initialize all lists of the graph as a empty vector.
	vector<int> init;
	vector<vector<int>> graph(N,init);
	rep(i,M){
		int a, b;
		cin >> a >> b;
		graph[a-1].emplace_back(b-1);
		graph[b-1].emplace_back(a-1);
	}
// rep(i,N)
//  putv(graph[i]);
	return graph;
}

ll Manhattan_dist(ll x1, ll y1, ll x2, ll y2){
	return abs(x1-x2) + abs(y1-y2);
}
void out(bool ans){
	if(ans == true) cout << "yes" << endl;
	else cout << "no" << endl;
}
void Out(bool ans){
	if(ans == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}
void OUT(bool ans){
	if(ans == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}
ll gcd(const ll a, const ll b){
	return (b==0) ? a : gcd(b,a%b);
}
ll lcm(const ll a, const ll b){
	return a*(b/gcd(a,b));
}
// イテレーティブな方法で適宜組んだ方が時間量領域量ともにセーブできる
// ll lcmv(vector<ll> vec){
// 	int t = vec.size();
// 	if(t==2)
// 		return lcm(vec[0],vec[1]);
// 	ll v = vec[t-1];
// 	vec.pop_back();
// 	return lcm(lcmv(vec),v);
// }
// ll gcdv(vector<ll> vec){
// 	int t = vec.size();
// 	if(t==1)
// 		return vec[0];
// 	if(t==2)
// 		return gcd(vec[0],vec[1]);
// 	ll v = vec[t-1];
// 	vec.pop_back();
// 	return gcd(gcdv(vec),v);
// }

// $\min\{s\in\mathbb{N}:p^s|n\}$
// nをpで何回割れるか
ll hmt_p_divide_n(ll p, ll n){
	ll s = 0;
	while(n%p == 0){
		n /= p;
		s++;
	}
	return s;
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct city {
	int n,p,y;
	bool operator<( const city& right ) const {
			return p==right.p ? y<right.y : p<right.p;
	}
};
bool n_comp( const city& left, const city& right ) {
	return left.n==right.n ? left<right : left.n<right.n;
}

int main(){
	int N,M;
	cin >> N>>M;
	vector<city> vec;
	rep(i,M){
		int p,y;
		cin >> p >> y;
		city c = {i,p,y};
		vec.emplace_back(c);
	}

// rep(i,M)
// 	cout<<fill(6)<<vec[i].p<<fill(6)<<vec[i].y<<endl;
// cout << endl;
	
	sort(vec.begin(),vec.end());

// rep(i,M)
// 	cout<<fill(6)<<vec[i].p<<fill(6)<<vec[i].y<<endl;
// cout << endl;

	int cp = vec[0].p;
	int cntr = 1;
	rep(i,M){
		if(vec[i].p != cp) cntr = 1;
		cp = vec[i].p;
		vec[i].y = cntr++;
	}

// rep(i,M)
// 	cout<<fill(6)<<vec[i].p<<fill(6)<<vec[i].y<<endl;
// cout << endl;

	sort(vec.begin(),vec.end(),n_comp);
	rep(i,M)
		cout<<fill(6)<<vec[i].p<<fill(6)<<vec[i].y<<endl;
}



Measured memory_bytes: 2804