// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

using namespace std;



typedef long long ll;

typedef pair<int, int> P;

typedef pair<int, double> Pid;

typedef pair<double, int> Pdi;

typedef pair<ll, int> Pl;

const double PI = 3.1415926535897932;   // acos(-1)

const double EPS = 1e-15;

const int INF = 1001001001;

const ll mod = 1e+9 + 7;



#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)

#define chadd(x, y) x = (x + y) % mod



vector<P> input[100005];



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int n, m;

    cin >> n >> m;

    for(int i = 0; i < m; ++i){

        int p, y;

        cin >> p >> y;

        input[p].push_back(P(y, i));

    }

    vector<P> output(m);

    for(int i = 1; i <= n; ++i){

        if(input[i].size() == 0)    continue;

        sort(input[i].begin(), input[i].end());

        int sz = input[i].size();

        for(int j = 0; j < sz; ++j){

            int id = input[i][j].second;

            output[id] = P(i, j+1);

        }

    }

    cout << fixed << setfill('0') << right << setw(6);

    for(int i = 0; i < m; ++i){

        cout << setfill('0') << right << setw(6) << output[i].first;

        cout << setfill('0') << right << setw(6) << output[i].second << "\n";

    }

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



typedef long long ll;

typedef uint64_t ull;

typedef pair<int, int> P;

constexpr double PI = 3.1415926535897932;   // acos(-1)

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int n, m;

    cin >> n >> m;

    vector<vector<P>> input(n + 1);

    for(int i = 0; i < m; ++i){

        int p, y;

        cin >> p >> y;

        input[p].push_back(P(y, i));

    }

    for(int i = 1; i <= n; ++i) sort(input[i].begin(), input[i].end());

    vector<ll> ans(m, 0);

    for(int i = 1; i <= n; ++i){

        int sz = input[i].size();

        for(int j = 0; j < sz; ++j){

            int y = input[i][j].first, id = input[i][j].second;

            ans[id] += (ll)i * 1000000;

            ans[id] += j + 1;

        }

    }

    for(int i = 0; i < m; ++i){

        cout << setfill('0') << right << setw(12);

        cout << ans[i] << "\n";

    }

}

// Fastest known solution for this problem: