using System;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Threading.Tasks;

/*
・概要
一次元（線上）の座標圧縮
座標間の空白の長さが情報として価値を有しない場合に、圧縮の意義あり。
（大小関係だけを抽出 / 左から何番目かだけを考える）
圧縮の計算量はO(N * logN)（Nは要素数）

（e.g.
圧縮前： [1000, 2000, 400, 100000, 30, 334, 2000]
圧縮後： [3, 4, 2, 5, 0, 1, 4]）

・使用法
1. 元の座標配列を引数として、CompCoord1Dクラスのオブジェクトを作成
　元の座標配列はlong配列とする。
（e.g. CompCoord1D coord = new CompCoord1D(arr);）

2. Compress関数で、元の座標配列を圧縮した配列を獲得。
　このとき、得られるのはint配列。
（e.g. int[] compressed = coord.Compress();）

3. 特定の座標の圧縮前の値を知りたい場合、Decompress関数を使用。
　入力された座標について、圧縮前の値を返す。
（e.g. long before = coord.Decompress(after);）

・アルゴリズム
各座標について、全体で何番目に大きいかを求めれば良い。
座標配列をソートし、重複した値を削除した上で、各座標についてそれが何番目か二分探索で求める。

*/

class Program
{
	//Main
	static void Main(string[] args)
	{
		//出力準備（AutoFlushを切る）
		var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false};
		Console.SetOut(sw);
		//解答
		Solve();
		//出力終了
		Console.Out.Flush();
	}

	static void Solve()
	{
		//読み込む
		string[] S = Console.ReadLine().Split(' ');
		int N = int.Parse(S[0]);
		int M = int.Parse(S[1]);

		//元のPの並びを格納する配列
		int[] arrP = new int[M];
		//各県の市番号のリスト
		List<long>[] cityNum = new List<long>[N];
		//出力用のキューの配列
		Queue<int>[] outQ = new Queue<int>[N];
		//初期化
		for(int i=0; i<N; i++){
			cityNum[i] = new List<long>();
			outQ[i] = new Queue<int>();
		}

		//読み込んで格納
		for(int i=0; i<M; i++){
			string[] Si = Console.ReadLine().Split(' ');
			int P = int.Parse(Si[0]) - 1;
			int Y = int.Parse(Si[1]);
			arrP[i] = P;
			cityNum[P].Add(Y);
		}

		//各県について、圧縮
		for(int i=0; i<N; i++){
			//市がない場合
			if(cityNum[i].Count() < 1){
				continue;
			}
			//ある場合、座標圧縮
			else{
				//圧縮
				CompCoord1D coord = new CompCoord1D(cityNum[i].ToArray());
				int[] comp = coord.Compress();

				//キューに格納
				foreach(int c in comp){
					outQ[i].Enqueue(c);
				}
			}
		}

		//出力
		foreach(int p in arrP){
			//対象となる県番号
			int pref = p + 1;
			//対象となる市番号
			int city = outQ[p].Dequeue() + 1;
			//0埋めして出力
			Console.WriteLine("{0:D6}{1:D6}", pref, city);
		}
	}
}


//座標配列を圧縮する為のクラス
/*
元の座標配列と、圧縮後の座標配列とを保持
Compress関数で座標を圧縮し、
Decompress関数で、特定の座標を復元する
*/
class CompCoord1D
{
	//元の座標配列を圧縮する
	/*
	引数は、元の座標を格納したlong配列。（e.g. [1000, 2000, 400, 100000, 30, 334, 2000]）
	これを圧縮する。（e.g. [3, 4, 2, 5, 0, 1, 4]）
	戻り値は、復元用の配列（e.g. [30, 334, 400, 1000, 2000, 100000]）
	→圧縮後の値をインデックスとすれば、圧縮前の値を取得できる。
	*/

	//元の配列
	private long[] original;
	//圧縮後の配列
	private int[] compressed;
	//圧縮済みを示すフラグ
	private bool compDone;
	//座標の復元用の配列
	private long[] values;

	//コンストラクタ
	public CompCoord1D(long[] arr){
		this.original = arr;
		this.compressed = new int[arr.Length];
	}

	//圧縮後の配列を返すメソッド
	public int[] Compress(){
		//圧縮を計算済みの場合
		if(compDone){
			return this.compressed;
		}

		//これから圧縮する場合
		else{
			//元の配列をソートした配列を作成
			long[] sorted = new long[this.original.Length];
			Array.Copy(this.original, sorted, this.original.Length);
			Array.Sort(sorted);

			//重複していない値だけを加えたリストを作成
			List<long> val = new List<long>();
			val.Add(sorted[0]);
			for(int i=1; i<sorted.Length; i++){
				if(sorted[i-1] != sorted[i]){
					val.Add(sorted[i]);
				}
			}

			//復元用の配列に変換
			this.values = val.ToArray();

			//二分探索により、元の座標の圧縮後の座標を特定し、配列に格納
			for(int i=0; i<original.Length; i++){
				compressed[i] = Array.BinarySearch(values, original[i]);
			}

			//圧縮済みフラグを立てる
			compDone = true;

			//圧縮後の配列を出力
			return this.compressed;
		}
	}

	//圧縮後の座標から、圧縮前の座標を求めるメソッド
	/*
	引数は、圧縮後の座標（int）
	戻り値は、圧縮前の座標（long）
	（対象が存在しない場合、-1を返す）
	*/
	public long Decompress(int idx){
		//対象が存在しない場合
		if(idx < 0 || idx >= this.original.Length){
			return -1;
		}
		//圧縮前の座標を返す
		else{
			return this.values[idx];
		}
	}
}



Measured memory_bytes: 45020