
import java.text.DecimalFormat;
import java.util.Scanner;


public class Main {

	static int[][] arr;
	
	static int M;
	
	static int N;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		DecimalFormat format= new DecimalFormat("000000");
		
		M=sc.nextInt();
		
		N=sc.nextInt();
		
		arr=new int[N][4];  // 1.辖区 2.年份 3.序号 4，结果
		
		for(int i=0; i<N; i++) {
			arr[i][0]=sc.nextInt();
			arr[i][1]=sc.nextInt();
			arr[i][2]=i;
			arr[i][3]=0;
			
		}
		
		for(int i=0; i<N-1 ; i++) {
			for(int j=0; j<N-1-i; j++) {
				if(arr[j][0] > arr[j+1][0]) {
					int[] temp =arr[j+1];
					arr[j+1]=arr[j];
					arr[j]=temp;
				}
			}
		}

		 // [[1, 32, 0, 0], [1, 12, 2, 0], [2, 63, 1, 0]]
		
		for(int i=0; i<N-1 ; i++) {
			for(int j=0; j<N-1-i; j++) {
				if(arr[j][0]== arr[j+1][0] && arr[j][1] > arr[j+1][1]) {
					int[] temp =arr[j+1];
					arr[j+1]=arr[j];
					arr[j]=temp;
				}
			}
		}
		
		 //arr  [[1, 12, 2, 0], [1, 32, 0, 0], [2, 63, 1, 0]]
		
		int temp=1;
		for(int i=0; i<N ;i++) {
			if(i+1 < N) {
				 if(arr[i][0] == arr[i+1][0]) {
					 arr[i][3]=temp;
					 arr[i+1][3]=temp+1;
					 temp++;
				 }else {
					 temp=1;
					 arr[i+1][3]=temp;
				 }
				 
			}
		}
		
		for(int i=0; i<N-1 ; i++) {
			for(int j=0; j<N-1-i; j++) {
				if(arr[j][2] > arr[j+1][2]) {
					int[] temp2 =arr[j+1];
					arr[j+1]=arr[j];
					arr[j]=temp2;
				}
			}
		}
		
		for(int i=0; i<N; i++) {
			System.out.println(format.format(arr[i][0])+""+format.format(arr[i][3]));
		}
		
	}
}