#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N, M;
int P[100000], Y[100000];
vector<int> yd[100001];
int main()
{
    //  scanf("%d%d", &N, &M);
    cin >> N >> M;
    for (int i = 0; i < M; i++)
        scanf("%d%d ", &P[i], &Y[i]), yd[P[i]].push_back(Y[i]);
    for (int i = 0; i < N; i++)
        sort(yd[i + 1].begin(), yd[i + 1].end());
    for (int i = 0; i < M; i++)
        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);
}