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

L=[[] for i in range(a)]

u=0

for i in range(b):

    u+=1

    c=list(map(int,input().split()))

    c.append(u)

    L[int(c[0])-1].append(c)

for i in L:

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

for i in L:

    e=0

    for j in i:

        e+=1

        j.append(e)

q=[]

for w in L:

   q.extend(w) 

q.sort(key=lambda x:x[2])

for r in range(b):

        print((str(q[r][0]).zfill(6)+str(q[r][3]).zfill(6)))
a,b=list(map(int,input().split()))

L=[[] for i in range(a)]

u=0

# i番目の県の情報（[i，年，入力順]）をLのi番目に入れる

for i in range(b):

    u+=1

    c=list(map(int,input().split()))

    c.append(u)

    L[int(c[0])-1].append(c)

# Lの要素を年でソート

for i in L:

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

#　ソートしたので、要素ごとに何番目にできたかを末尾に付け加えておく

for i in L:

    e=0

    for j in i:

        e+=1

        j.append(e)

q=[]

for w in L:

   q.extend(w)# flatten

# 入力順に並べ替えて、入力した順に出力できるようにする

q.sort(key=lambda x:x[2])

for r in range(b):

        print((str(q[r][0]).zfill(6)+str(q[r][3]).zfill(6)))# zfill
a, b = list(map(int, input().split()))
L = [[] for i in range(a)]
u = 0
for i in range(b):
    u += 1
    c = list(map(int, input().split()))
    c.append(u)
    L[int(c[0]) - 1].append(c)
for i in L:
    i.sort(key=lambda x: x[1])
for i in L:
    e = 0
    for j in i:
        e += 1
        j.append(e)
q = []
for w in L:
    q.extend(w)
q.sort(key=lambda x: x[2])
for r in range(b):
    print((str(q[r][0]).zfill(6) + str(q[r][3]).zfill(6)))

a, b = list(map(int, input().split()))
L = [[] for i in range(a)]
u = 0
# i番目の県の情報（[i，年，入力順]）をLのi番目に入れる
for i in range(b):
    u += 1
    c = list(map(int, input().split()))
    c.append(u)
    L[int(c[0]) - 1].append(c)
# Lの要素を年でソート
for i in L:
    i.sort(key=lambda x: x[1])
# 　ソートしたので、要素ごとに何番目にできたかを末尾に付け加えておく
for i in L:
    e = 0
    for j in i:
        e += 1
        j.append(e)
q = []
for w in L:
    q.extend(w)  # flatten
# 入力順に並べ替えて、入力した順に出力できるようにする
q.sort(key=lambda x: x[2])
for r in range(b):
    print((str(q[r][0]).zfill(6) + str(q[r][3]).zfill(6)))  # zfill

+# i番目の県の情報（[i，年，入力順]）をLのi番目に入れる +# Lの要素を年でソート +# 　ソートしたので、要素ごとに何番目にできたかを末尾に付け加えておく -    q.extend(w) +    q.extend(w)  # flatten +# 入力順に並べ替えて、入力した順に出力できるようにする -    print((str(q[r][0]).zfill(6) + str(q[r][3]).zfill(6))) +    print((str(q[r][0]).zfill(6) + str(q[r][3]).zfill(6)))  # zfill