import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int n, m; readV(n, m);
  struct C { int p, y, i, b; }
  auto c = new C[](m);
  foreach (i; 0..m) {
    int p, y; readV(p, y);
    c[i] = C(p, y, i, 0);
  }

  c.sort!"a.y<b.y";

  auto b = new int[](n+1);
  foreach (ref ci; c) ci.b = ++b[ci.p];

  c.sort!"a.i<b.i";

  foreach (ci; c)
    writefln("%06d%06d", ci.p, ci.b);
}
