// C Library
#include <cassert> // (assert.h) C Diagnostics Library (header)
#include <cctype> // (ctype.h) Character handling functions (header)
#include <cerrno> // (errno.h) C Errors (header)
#include <cfloat> // (float.h) Characteristics of floating-point types (header)
#include <ciso646> // (iso646.h) ISO 646 Alternative operator spellings (header)
#include <climits> // (limits.h) Sizes of integral types (header)
#include <clocale> // (locale.h) C localization library (header)
#include <cmath> // (math.h) C numerics library (header)
#include <csetjmp> // (setjmp.h) Non local jumps (header)
#include <csignal> // (signal.h) C library to handle signals (header)
#include <cstdarg> // (stdarg.h) Variable arguments handling (header)
#include <cstdbool> // (stdbool.h) Boolean type (header)
#include <cstddef> // (stddef.h) C Standard definitions (header)
#include <cstdint> // (stdint.h) Integer types (header)
#include <cstdio> // (stdio.h) C library to perform Input/Output operations (header)
#include <cstdlib> // (stdlib.h) C Standard General Utilities Library (header)
#include <cstring> // (string.h) C Strings (header)
#include <ctime> // (time.h) C Time Library (header)
//#include <cuchar> // (uchar.h) Unicode characters (header)
#include <cwchar> // (wchar.h) Wide characters (header)
#include <cwctype> // (wctype.h) Wide character type (header)

// Containers
#include <array> // Array header (header)
#include <bitset> // Bitset header (header)
#include <deque> // Deque header (header)
#include <forward_list> // Forward list (header)
#include <list> // List header (header)
#include <map> // Map header (header)
#include <queue> // Queue header (header)
#include <set> // Set header (header)
#include <stack> // Stack header (header)
#include <unordered_map> //Unordered map header (header)
#include <unordered_set> // Unordered set header (header)
#include <vector> // Vector header (header)

// Input/Output Stream Library
#include <iostream> // The class relies on a single streambuf object for both the input and output operations.
#include <fstream> // Input/output stream class to operate on files.
#include <sstream> //

// Miscellaneous headers
#include <algorithm> // Standard Template Library: Algorithms (library )
#include <chrono> // Time library (header)
//#include <codecvt> // Unicode conversion facets (header)
#include <complex> // Complex numbers library (header)
#include <exception> // Standard exceptions (header)
#include <functional> // Function objects (header)
#include <initializer_list> // Initializer list (header)
#include <iterator> // Iterator definitions (header)
#include <limits> // Numeric limits (header)
#include <locale> // Localization library (header)
#include <memory> //Memory elements (header)
#include <new> // Dynamic memory (header)
#include <numeric> // Generalized numeric operations (header)
#include <random> // Random (header)
#include <ratio> // Ratio header (header)
#include <regex> // Regular Expressions (header)
#include <stdexcept> // Exception classes (header)
#include <string> // Strings (header)
#include <system_error> // System errors (header)
#include <tuple> // Tuple library (header)
#include <typeinfo> // Type information (header)
#include <type_traits> //type_traits (header)
#include <utility> // Utility components (header)
#include <valarray> // Library for arrays of numeric values (header)
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0);
#define END return EXIT_SUCCESS;
#define FOR(I,A,B) for(int (I)=(A);(I)<(B);++(I))
#define ALL(C) (C).begin(),(C).end()
#define INPUT(P) cin>>(P);
#define INPUT2(P1,P2) cin>>(P1)>>(P2);
#define INPUT3(P1,P2,P3) std::cin>>(P1)>>(P2)>>(P3);
#define INPUTS(I,A,B,V) FOR(I,A,B)cin>>V[I];
#define OUTPUT(P) std::cout<<P<<std::endl;
#define OUTPUTS(I,A,B,V) FOR(I,A,B)cout<<V[i]<<endl;
typedef long long ll;
typedef pair<int, int> P;
class Data {
private:
public:
  int id;
  int P;
  int Y;
  int n;
};
bool cmp(const Data &a, const Data &b) {
  return a.P == b.P ? a.Y < b.Y : a.P < b.P;
}
bool cmp2(const Data &a, const Data &b) {
  return a.id < b.id;
}
inline void solve()
{
  int N, M;
  INPUT2(N,M)
  vector<Data> v(M);
  FOR(i,0,M) {
    Data tmp;
    cin>>tmp.P>>tmp.Y;
    tmp.id = i;
    v[i] = tmp;
  }
  sort(ALL(v), cmp);
  int P;
  int cnt = 1;
  FOR(i,0,M) {
    if (i == 0) {
      P = v[i].P;
      v[i].n = cnt;
      cnt++;
      continue;
    }
    int NP = v[i].P;
    if (P != NP) {
      cnt = 1;
      P = NP;
    }
    v[i].n = cnt;
    cnt++;
  }
  sort(ALL(v), cmp2);
  FOR(i,0,M) {
    cout<<setfill('0')<<right<<setw(6)<<v[i].P;
    cout<<setfill('0')<<right<<setw(6)<<v[i].n<<endl;
  }
}
int main(int argc,char**argv)
{
  BEGIN
  solve();
  END
}
// $g++ -Wall -O2 -std=c++17 template.cpp


Measured memory_bytes: 3072