#include <bits/stdc++.h>

#define mod 1000000007

#define rep(i, n) for(int i=0; i<n; ++i)

using namespace std;
typedef long long ll; 
 
int main(void){
	
	int N, M;
	
	cin >> N >> M;
	
	int P[M], Y[M];
	vector<int> yd[N + 1];
	
	rep(i, M){
		cin >> P[i] >> Y[i];
		yd[P[i]].push_back(Y[i]);
	}
	
	rep(i, N)
		sort(yd[i + 1].begin(), yd[i + 1].end());
	
	rep(i, M)
		printf("%012lld\n", ll(P[i]) * 1000000 + int(lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]) - yd[P[i]].begin()) + 1);
		
	return 0;
}