from collections import Counter,defaultdict,deque

from heapq import heappop,heappush,heapify

import sys,bisect,math,itertools,fractions,pprint

sys.setrecursionlimit(10**8)

mod = 10**9+7

mod2 = 998244353

INF = float('inf')

def inp(): return int(sys.stdin.readline())

def inpl(): return list(map(int, sys.stdin.readline().split()))

def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))



n,m = inpl()

p = []

res = [[] for i in range(m)]

for i in range(m):

    a,b = inpl()

    p.append((a,b,i))

p.sort(key=lambda x:x[1])

p.sort(key=lambda x:x[0])

cnt = 0

tmp = 0

for i,j in enumerate(p):

    if i == 0:

        tmp = j[0]

    if tmp == j[0]:

        cnt += 1

    else:

        tmp = j[0]

        cnt = 1

    res[j[2]] = [j[0],cnt] 

for i in res:

    print(('{}{}'.format(str(i[0]).zfill(6),str(i[1]).zfill(6))))
from collections import Counter,defaultdict,deque

from heapq import heappop,heappush,heapify

import sys,bisect,math,itertools,fractions,pprint

sys.setrecursionlimit(10**8)

mod = 10**9+7

mod2 = 998244353

INF = float('inf')

def inp(): return int(sys.stdin.readline())

def inpl(): return list(map(int, sys.stdin.readline().split()))

def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))



n,m = inpl()

p = []

res = [[] for i in range(m)]

for i in range(m):

    a,b = inpl()

    p.append((a,b,i))

p.sort()

cnt = 0

tmp = 0

for i,j in enumerate(p):

    if i == 0:

        tmp = j[0]

    if tmp == j[0]:

        cnt += 1

    else:

        tmp = j[0]

        cnt = 1

    res[j[2]] = [j[0],cnt] 

for i in res:

    print(('{}{}'.format(str(i[0]).zfill(6),str(i[1]).zfill(6))))
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heapify
import sys, bisect, math, itertools, fractions, pprint

sys.setrecursionlimit(10**8)
mod = 10**9 + 7
mod2 = 998244353
INF = float("inf")


def inp():
    return int(sys.stdin.readline())


def inpl():
    return list(map(int, sys.stdin.readline().split()))


def inpln(n):
    return list(int(sys.stdin.readline()) for i in range(n))


n, m = inpl()
p = []
res = [[] for i in range(m)]
for i in range(m):
    a, b = inpl()
    p.append((a, b, i))
p.sort(key=lambda x: x[1])
p.sort(key=lambda x: x[0])
cnt = 0
tmp = 0
for i, j in enumerate(p):
    if i == 0:
        tmp = j[0]
    if tmp == j[0]:
        cnt += 1
    else:
        tmp = j[0]
        cnt = 1
    res[j[2]] = [j[0], cnt]
for i in res:
    print(("{}{}".format(str(i[0]).zfill(6), str(i[1]).zfill(6))))

from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heapify
import sys, bisect, math, itertools, fractions, pprint

sys.setrecursionlimit(10**8)
mod = 10**9 + 7
mod2 = 998244353
INF = float("inf")


def inp():
    return int(sys.stdin.readline())


def inpl():
    return list(map(int, sys.stdin.readline().split()))


def inpln(n):
    return list(int(sys.stdin.readline()) for i in range(n))


n, m = inpl()
p = []
res = [[] for i in range(m)]
for i in range(m):
    a, b = inpl()
    p.append((a, b, i))
p.sort()
cnt = 0
tmp = 0
for i, j in enumerate(p):
    if i == 0:
        tmp = j[0]
    if tmp == j[0]:
        cnt += 1
    else:
        tmp = j[0]
        cnt = 1
    res[j[2]] = [j[0], cnt]
for i in res:
    print(("{}{}".format(str(i[0]).zfill(6), str(i[1]).zfill(6))))

-p.sort(key=lambda x: x[1]) -p.sort(key=lambda x: x[0]) +p.sort()