#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
struct
{
    int p, y;
} a[N];
vector<pair<int, int>> v[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
        scanf("%d%d", &a[i].p, &a[i].y);
    for (int i = 0; i < m; i++)
        v[a[i].p].push_back({a[i].y, i});
    for (int i = 1; i <= n; i++)
        sort(v[i].begin(), v[i].end());
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < v[i].size(); j++)
            a[v[i][j].second].y = j + 1;
    for (int i = 0; i < m; i++)
        printf("%06d%06d\n", a[i].p, a[i].y);
    return 0;
}