N,M = list(map(int, input().split()))

 

pref = [[0] for i in range(N+1)]

q=[]



for i in range(M):

    p,y = list(map(int, input().split()))

    pref[p].append(y)

    q.append([p,y])

for p in pref:

    p.sort()

 

import bisect

for p,y in q:

    print(("%06d%06d" %(p, bisect.bisect_left(pref[p], y))))
import sys

input=sys.stdin.readline

 

N,M = list(map(int, input().split()))

 

pref = [[0] for i in range(N+1)]

import collections

q = collections.deque()

 

for i in range(M):

    p,y = list(map(int, input().split()))

    pref[p].append(y)

    q.append((p,y))

for p in pref:

    p.sort()

 

import bisect

for p,y in q:

    print(("%06d%06d" %(p, bisect.bisect_left(pref[p], y))))
N, M = list(map(int, input().split()))
pref = [[0] for i in range(N + 1)]
q = []
for i in range(M):
    p, y = list(map(int, input().split()))
    pref[p].append(y)
    q.append([p, y])
for p in pref:
    p.sort()
import bisect

for p, y in q:
    print(("%06d%06d" % (p, bisect.bisect_left(pref[p], y))))

import sys

input = sys.stdin.readline
N, M = list(map(int, input().split()))
pref = [[0] for i in range(N + 1)]
import collections

q = collections.deque()
for i in range(M):
    p, y = list(map(int, input().split()))
    pref[p].append(y)
    q.append((p, y))
for p in pref:
    p.sort()
import bisect

for p, y in q:
    print(("%06d%06d" % (p, bisect.bisect_left(pref[p], y))))

+import sys + +input = sys.stdin.readline -q = [] +import collections + +q = collections.deque() -    q.append([p, y]) +    q.append((p, y))