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

ken = []

for i in range(m):

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

    ken.append([p,y,i+1])



k = sorted(ken)

a = []

cnt = 1

for i in range(m):

    if i >= 1:

        if k[i][0] == k[i-1][0]:

            cnt += 1

        else:

            cnt = 1

    a.append([k[i][-1],k[i][0],cnt])

    

aa = sorted(a)

b = []

for i in range(m):

    b.append([aa[i][1],aa[i][2]])



for i in range(m):

    print(("{0:06d}".format(b[i][0]) + "{0:06d}".format(b[i][1])))
n,m = list(map(int,input().split()))

ken = []

for i in range(m):

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

    ken.append([p,y,i+1])

 

k = sorted(ken)

a = []

cnt = 1

for i in range(m):

    if i >= 1:

        if k[i][0] == k[i-1][0]:

            cnt += 1

        else:

            cnt = 1

    a.append([k[i][-1],k[i][0],cnt])



aa = sorted(a)

for i in range(m):

    print(("{0:06d}".format(aa[i][1]) + "{0:06d}".format(aa[i][2])))
n, m = list(map(int, input().split()))
ken = []
for i in range(m):
    p, y = list(map(int, input().split()))
    ken.append([p, y, i + 1])
k = sorted(ken)
a = []
cnt = 1
for i in range(m):
    if i >= 1:
        if k[i][0] == k[i - 1][0]:
            cnt += 1
        else:
            cnt = 1
    a.append([k[i][-1], k[i][0], cnt])
aa = sorted(a)
b = []
for i in range(m):
    b.append([aa[i][1], aa[i][2]])
for i in range(m):
    print(("{0:06d}".format(b[i][0]) + "{0:06d}".format(b[i][1])))

n, m = list(map(int, input().split()))
ken = []
for i in range(m):
    p, y = list(map(int, input().split()))
    ken.append([p, y, i + 1])
k = sorted(ken)
a = []
cnt = 1
for i in range(m):
    if i >= 1:
        if k[i][0] == k[i - 1][0]:
            cnt += 1
        else:
            cnt = 1
    a.append([k[i][-1], k[i][0], cnt])
aa = sorted(a)
for i in range(m):
    print(("{0:06d}".format(aa[i][1]) + "{0:06d}".format(aa[i][2])))

-b = [] -    b.append([aa[i][1], aa[i][2]]) -for i in range(m): -    print(("{0:06d}".format(b[i][0]) + "{0:06d}".format(b[i][1]))) +    print(("{0:06d}".format(aa[i][1]) + "{0:06d}".format(aa[i][2])))