#include <iostream>
#include <stdio.h>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <string>
#include <queue>
#include <functional>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
using namespace std;

//	英語は 26 文字

//	common
namespace{
	#define		CAST( T, val )		( (T)( val ) )
	#define		CASE( lb )			break; case lb:
	#define		CASE_CONT( lb )		case lb:
	#define		CASE_DEF			break; default:
	#define		For( i, s )			for(int i= 0, forEnd##i= CAST( int, s ); i< forEnd##i; ++i)
	#define		ForA( i, a, s )		for(int i= CAST( int, a ), forEnd##i= CAST( int, s ); i< forEnd##i; ++i)
	#define		ForR( i, s )		for(int i= s; i>= 0; i--)
	#define		ForRA( i, s, e )	for(int i= s; i>= e; i--)
	#define		ForItr( itr, con )	for(auto itr= con.begin(), forEnd##itr= con.end(); itr!= forEnd##itr; ++itr)
	#define		ForRItr( itr, con )	for(auto itr= con.rbegin(), forEnd##itr= con.rend(); itr!= forEnd##itr; ++itr)
	#define		ForStr( i, str )	for(int i= 0; str[i]; ++i)
	#define		GOTO( lb )			goto lb
	#define		LABEL( lb )			lb:
	#define		ALL( con )			(con).begin(), (con).end()

	template <typename T, typename K> struct Pair{ T fst; K snd; };
	template<typename T, typename K> std::istream& operator >>(std::istream& in, Pair<T,K>& p){ return in>> p.fst>> p.snd; }

	typedef		long long			xint;
	typedef		unsigned long long	uxint;
	typedef		unsigned int		uint;
	typedef		unsigned char		uchar;
	typedef		unsigned short		ushort;
	typedef		vector<int>			Vi;
	typedef		vector<double>		Vd;
	typedef		Pair<int,int>		Pii;
	typedef		vector<Pii>			VPii;

	const int Ten5 = 100000;		//	10^5
	const int Ten6 = 1000000;	//	10^6
	const double EPS = 0.00000000023283064365386962890625;	//	2^-32
}
//	合同式, MaxMin
namespace c{
	//	合同式
	class Mod{public:
		typedef	int	Type;	//	型
		static Type N;	//	法

		const Mod operator +(const Mod& m) const{ return Mod(x+m.x); }
		const Mod& operator +=(const Mod& m){ return *this= Mod(x+m.x); }
		Mod operator -(const Mod& m) const{ return Mod(x-m.x+N); }
		const Mod& operator -=(const Mod& m){ return *this= Mod(x-m.x+N); }
		Mod operator *(const Mod& m) const{ return Mod(x*m.x); }
		const Mod& operator *=(const Mod& m){ return *this= Mod(x*m.x); }
		Mod operator /(const Mod& m) const{ //	フェルマーの小定理より, m.x の逆元は m.x^( HOU-2 )
			const Type n= N-2; Type p= m.x, r= x; for(Type b= 1; b< n; b<<= 1){ if( n & b ) r= r*p%N; p= p*p%N; } return r;
		}
		const Mod& operator /=(const Mod& m){ return *this= *this /m; }
		operator const Type&() const{return x;}
		Mod(){}
		Mod(Type v):x(v%N){}
	private:Type x;}; Mod::Type Mod::N= 1000 *1000 *1000 +7;
	//	最大値
	template <typename T> class Max{public:
		//	何回更新したか
		int cnt() const{return c;}

		//	更新したときに true を返す
		bool operator =(const T&v){if(!c){c=1;x=v;return true;}if(x<v){c++;x=v;return true;}return false;}

		operator const T&() const{return x;}
		Max():x(0),c(0){}
		Max(const T&v):x(v),c(1){}
		Max(const T*f,const T*l):x(*f++),c(1){while(f<l){*this=*f++;}}
		Max(const T*a,int n):x(0),c(0){For(i,n)*this=*a++;}
	private:T x;int c;};
	//	最小値
	template <typename T> class Min{public:
		//	何回更新したか
		int cnt() const{return c;}

		//	更新したときに true を返す
		bool operator =(const T&v){if(!c){c=1;x=v;return true;}if(v<x){c++;x=v;return true;}return false;}

		operator const T&() const{return x;}
		Min():x(0),c(0){}
		Min(const T&v):x(v),c(1){}
		Min(const T*f,const T*l):x(*f++),c(1){while(f<l){*this=*f++;}}
		Min(const T*a,int n):x(0),c(0){For(i,n)*this=*a++;}
	private:T x;int c;};
	istream& operator >>(istream&in,Mod&m){Mod::Type t;in>>t;m=Mod(t);return in;}
	ostream& operator <<(ostream&ot,const Mod&m){return ot<<CAST(Mod::Type,m);}
	template <typename T> istream& operator >>(istream&in,Max<T>&m){T t;in>>t;m=Max<T>(t);return in;}
	template <typename T> ostream& operator <<(ostream&ot,const Max<T>&m){return ot<<CAST(T,m);}
	template <typename T> istream& operator >>(istream&in,Min<T>&m){T t;in>>t;m=Min<T>(t);return in;}
	template <typename T> ostream& operator <<(ostream&ot,const Min<T>&m){return ot<<CAST(T,m);}
}
//	Vec
namespace c{
	//	2D int Vector
	class Pint{
	public:
		int x, y;
		static const Pint dir[8];

		//	util
		static void fldWH(const int width, const int height){ Width= width; Height= height; }
		inline bool isInFld() const{ return 0 <= x && x < Width && 0 <= y && y < Height; }
		inline void swap(){ int t= x; x= y; y= t; }

		//	vector
		inline double len() const{ return sqrt( sq() ); }
		inline double len(const Pint& p) const{ return sqrt( sq(p) ); }
		inline int sq() const{ return x*x+y*y; }
		inline int sq(const Pint& p) const{ return (x-p.x)*(x-p.x) +(y-p.y)*(y-p.y); }
		inline int manhattan() const{ return abs(x) +abs(y); }
		inline int manhattan(const Pint& p) const{ return abs(x-p.x) +abs(y-p.y); }
		inline int dot(const Pint& p) const{ return x*p.x+y*p.y; }
		inline int crs(const Pint& p) const{ return x*p.y-y*p.x; }

		//	opr, cst
		inline Pint operator +(){ return Pint( x, y ); }
		inline Pint operator -(){ return Pint( -x, -y ); }
		inline Pint operator +(const Pint& p) const{ return Pint( x+p.x, y+p.y ); }
		inline const Pint& operator +=(const Pint& p){ x+= p.x; y+= p.y; return *this; }
		inline Pint operator -(const Pint& p) const{ return Pint( x-p.x, y-p.y ); }
		inline const Pint& operator -=(const Pint& p){ x-= p.x; y-= p.y; return *this; }
		inline Pint operator *(const Pint& p) const{ return Pint( x*p.x, y*p.y ); }
		inline const Pint& operator *=(const Pint& p){ x*= p.x; y*= p.y; return *this; }
		inline Pint operator /(const Pint& p) const{ return Pint( x/p.x, y/p.y ); }
		inline const Pint& operator /=(const Pint& p){ x/= p.x; y/= p.y; return *this; }
		inline Pint operator *(const int k) const{ return Pint( x*k, y*k ); }
		inline const Pint& operator *=(const int k){ x*= k; y*= k; return *this; }
		inline Pint operator /(const int k) const{ return Pint( x/k, y/k ); }
		inline const Pint& operator /=(const int k){ x/= k; y/= k; return *this; }
		inline bool operator <(const Pint& p) const{ return x== p.x ? y<p.y : x<p.x; }
		inline bool operator >(const Pint& p) const{ return x== p.x ? y>p.y : x>p.x; }
		inline bool operator ==(const Pint& p) const{ return x==p.x && y==p.y; }
		inline bool operator !=(const Pint& p) const{ return x!=p.x || y!=p.y; }
		Pint(){}
		Pint(const int x, const int y) : x(x), y(y){}
		
	private:
		static int Width, Height;
	};
	istream& operator >>(istream& in, Pint& p){
		return in>> p.x>> p.y;
	}
	ostream& operator <<(ostream& out, const Pint& p){
		return out<< "( "<< p.x<< ", "<< p.y<< " )";
	}
	int Pint::Width, Pint::Height;
	const Pint Pint::dir[8]= { Pint(0,1),Pint(1,0),Pint(0,-1),Pint(-1,0),Pint(1,1),Pint(1,-1),Pint(-1,1),Pint(-1,-1) };

	//	2D double Vector
	class Pdouble{
	public:
		double x, y;

		//	vector
		inline double len() const{ return sqrt( sq() ); }
		inline double len(const Pdouble& p) const{ return sqrt( sq(p) ); }
		inline double sq() const{ return x*x+y*y; }
		inline double sq(const Pdouble& p) const{ return (x-p.x)*(x-p.x) +(y-p.y)*(y-p.y); }
		inline Pdouble norm(const double l= 1.0){ return *this * l /len(); }
		inline double dot(const Pdouble& p) const{ return x*p.x+y*p.y; }
		inline double crs(const Pdouble& p) const{ return x*p.y-y*p.x; }
		inline Pdouble proj(const Pdouble& v) const{
			const double s= v.sq();
			if( s < EPS*EPS ) return Pdouble( 0, 0 );
			return v *dot( v ) /s;
		}
		inline Pdouble rot(const double rad) const{ const double c= cos( rad ), s= sin( rad ); return Pdouble( c*x-s*y, s*x+c*y ); }

		//	opr, cst
		inline Pdouble operator +(){ return Pdouble( x, y ); }
		inline Pdouble operator -(){ return Pdouble( -x, -y ); }
		inline Pdouble operator +(const Pdouble& p) const{ return Pdouble( x+p.x, y+p.y ); }
		inline const Pdouble& operator +=(const Pdouble& p){ x+= p.x; y+= p.y; return *this; }
		inline Pdouble operator -(const Pdouble& p) const{ return Pdouble( x-p.x, y-p.y ); }
		inline const Pdouble& operator -=(const Pdouble& p){ x-= p.x; y-= p.y; return *this; }
		inline Pdouble operator *(const Pdouble& p) const{ return Pdouble( x*p.x, y*p.y ); }
		inline const Pdouble& operator *=(const Pdouble& p){ x*= p.x; y*= p.y; return *this; }
		inline Pdouble operator /(const Pdouble& p) const{ return Pdouble( x/p.x, y/p.y ); }
		inline const Pdouble& operator /=(const Pdouble& p){ x/= p.x; y/= p.y; return *this; }
		inline Pdouble operator *(const double k) const{ return Pdouble( x*k, y*k ); }
		inline const Pdouble& operator *=(const double k){ x*= k; y*= k; return *this; }
		inline Pdouble operator /(const double k) const{ return Pdouble( x/k, y/k ); }
		inline const Pdouble& operator /=(const double k){ x/= k; y/= k; return *this; }
		inline bool operator <(const Pdouble& p) const{ return x== p.x ? y<p.y : x<p.x; }
		inline bool operator >(const Pdouble& p) const{ return x== p.x ? y>p.y : x>p.x; }
		inline bool operator ==(const Pdouble& p) const{ return x==p.x && y==p.y; }
		inline bool operator !=(const Pdouble& p) const{ return x!=p.x || y!=p.y; }
		Pdouble(){}
		Pdouble(const double x, const double y) : x(x), y(y){}
		Pdouble(const Pint& p) : x(p.x), y(p.y){}
	};
	istream& operator >>(istream& in, Pdouble& p){
		return in>> p.x>> p.y;
	}
	ostream& operator <<(ostream& out, const Pdouble& p){
		return out<< "( "<< p.x<< ", "<< p.y<< " )";
	}

	//	( lP, lQ ) と ( nP, nQ ) の線分の交差判定
	bool CollisionLine(const Pdouble lP, const Pdouble lQ, const Pdouble nP, const Pdouble nQ){
		auto sign= [](double d){ return d < 0 ? -1 : d > 0 ? 1 : 0; };
		Pdouble v= lQ-lP; if( sign( v.crs( nP -lP ) )== sign( v.crs( nQ -lQ ) ) ) return false;
		v= nQ -nP; return sign( v.crs( lP -nP ) ) * sign( v.crs( lQ -nP ) ) <= 0;
	}
}
//	UnionFind, SegmentTree, 累積和
namespace c{
	//	Union Find
	class UnionFind{
	public:
		//	x, y は同じ
		void uniom(int x, int y){ mP[ find(x) ]= find(y); }
		//	x の親を取得
		int find(int x){ return mP[x]== x ? x : mP[x]= find( mP[x] ); }
		//	x が属する集合の親を x にする
		void toBeParent(int x){ mP[ find( x ) ]= x; mP[x]= x; }

		//	要素数 N, [ 0, N )
		UnionFind(int N) : mP(N){ For( i, N ) mP[i]= i; }
	private:
		std::vector<int> mP;
	};
	//	SegmentTree
	template <typename T, T Calc(T,T)> class SegTree{
		//	使い方
		//	SegTree<int, Gcd> tr( N );
		//	For( i, N ) tr.add( x );
		//	tr.setup();
		//	tr.get( i, k );

		//	root の idx を 1 からにするといろいろ楽
		//	- 配列のサイズは N*2
		//	- 生データが始まるのは idx= N から
		//	- 親子のノードが辿りやすい. 親(i) -> 子( 2i, 2i+1 ), 子(i) -> 親(i/2)
	public:
		//	要素を加える O(1). idx ∈ [ 0, N )
		inline void add(int idx, T x){
			mAr[idx +mStt]= x;
		}
		//	準備 O(N)
		void setup(){
			std::vector<bool> has( mStt *2, false );
			ForA( i, mStt, mStt +mN ) has[i]= true;

			for(int st= mStt /2, gl= mStt; st>= 1; st/= 2, gl/= 2){
				for(int idx= st; idx < gl; idx++){
					const int lft= idx *2;
					const int rgt= lft +1;

					if( has[lft] ){
						mAr[idx]= has[rgt] ? Calc( mAr[lft], mAr[rgt] ) : mAr[lft];
						has[idx]= true;
					}
				}
			}
		}
		//	[ lft, rgt ) の区間の結果を返す O(log N). lft, rgt ∈ [ 0, N )
		inline T get(int lft, int rgt) const{
			mLft= lft; mRgt= rgt;
			return getImpl( 0, mStt, 1 );
		}
		//	要素数 N
		SegTree(int N, T initVal= T()) : mN(N), mStt(N){
			if( ( mStt & ( mStt -1 ) ) != 0 ){
				mStt|= mStt >> 1;
				mStt|= mStt >> 2;
				mStt|= mStt >> 4;
				mStt|= mStt >> 8;
				mStt|= mStt >> 16;
				mStt++;
			}
			mAr.resize( mStt *2, initVal );
		}
		T operator [](int idx) const{ return mAr[idx+mStt]; }

	private:
		T getImpl(int bot, int top, int idx) const{
			if( mLft <= bot && top <= mRgt ) return mAr[idx];

			const int mid= ( bot +top ) /2;
			const int lft= idx *2;
			const int rgt= idx *2 +1;

			if( mid <= mLft ){
				return getImpl( mid, top, rgt );
			}else if( mRgt <= mid ){
				return getImpl( bot, mid, lft );
			}else{
				return Calc( getImpl( bot, mid, lft ), getImpl( mid, top, rgt ) );
			}
		}

		std::vector<T> mAr;
		int mN, mStt;

		mutable int mLft, mRgt;
	};
	//	累積和の class はありゃせん
}
using namespace c;


struct Data{
	int year;
	int idx;
	int pref;
	int no;
} dts[Ten5];
int main(){
	int N, M;
	Data* dt= dts;

	cin>> N>> M;
	For( i, M ){
		cin>> dt[i].pref>> dt[i].year;
		dt[i].idx= i;
	}

	std::sort( dt, dt +M, [](const Data& d, const Data& t){
		return d.year < t.year;
	});
	int cnt[Ten5+1]= {};
	For( i, M ){
		dt[i].no= ++cnt[dt[i].pref];
	}

	std::sort( dt, dt +M, [](const Data& d, const Data& t){
		return d.idx < t.idx;
	});
	For( i, M ){
		printf( "%06d%06d\n", dt[i].pref, dt[i].no );
	}

	return 0;
}


Measured memory_bytes: 3456