import bisect

import collections

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

L=collections.defaultdict(list)

p=[[int(j) for j in input().split()] for i in range(M)]

for x,y in sorted(p):

    L[x]+=[y]

for x,y in p:

    z=bisect.bisect(L[x],y)

    print(("%06d%06d"%(x,z)))

import sys

import collections

import bisect as bs

input=sys.stdin.readline

n,m=list(map(int,input().split()))

d=collections.defaultdict(list)

L=[]

for i in range(m):

    a,b=list(map(int,input().split()))

    L.append((a,b))

for x,y in sorted(L):

    d[x].append(y)

for x,y in L:

    z=bs.bisect(d[x],y)

    print(("%06d%06d"%(x,z)))
import bisect
import collections

N, M = list(map(int, input().split()))
L = collections.defaultdict(list)
p = [[int(j) for j in input().split()] for i in range(M)]
for x, y in sorted(p):
    L[x] += [y]
for x, y in p:
    z = bisect.bisect(L[x], y)
    print(("%06d%06d" % (x, z)))

import sys
import collections
import bisect as bs

input = sys.stdin.readline
n, m = list(map(int, input().split()))
d = collections.defaultdict(list)
L = []
for i in range(m):
    a, b = list(map(int, input().split()))
    L.append((a, b))
for x, y in sorted(L):
    d[x].append(y)
for x, y in L:
    z = bs.bisect(d[x], y)
    print(("%06d%06d" % (x, z)))

-import bisect +import sys +import bisect as bs -N, M = list(map(int, input().split())) -L = collections.defaultdict(list) -p = [[int(j) for j in input().split()] for i in range(M)] -for x, y in sorted(p): -    L[x] += [y] -for x, y in p: -    z = bisect.bisect(L[x], y) +input = sys.stdin.readline +n, m = list(map(int, input().split())) +d = collections.defaultdict(list) +L = [] +for i in range(m): +    a, b = list(map(int, input().split())) +    L.append((a, b)) +for x, y in sorted(L): +    d[x].append(y) +for x, y in L: +    z = bs.bisect(d[x], y)