# import bisect

# from collections import Counter, deque

# import copy

# from fractions import gcd

# from functools import reduce

# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

# import math

# import numpy as np

import sys

sys.setrecursionlimit(10 ** 5 + 10)

# input = sys.stdin.readline



def resolve():

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

    P=[]

    city_count=[0]*N

    city_end=[1]*N

    for i in range(M):

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

        city_count[p-1]+=1

        P.append([p,y])



    P1 = sorted(P, key=lambda x: x[1])

    P1=sorted(P1)

    for i in P1:

        i.append(city_end[i[0]-1])

        city_end[i[0] - 1]+=1





    for i in P:

        print((str(i[0]).zfill(6)+str(i[2]).zfill(6)))





    #P = dict(sorted(P.items()))



resolve()
# import bisect

# from collections import Counter, deque

# import copy

# from fractions import gcd

# from functools import reduce

# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

# import math

# import numpy as np

import sys



sys.setrecursionlimit(10 ** 5 + 10)





# input = sys.stdin.readline



def resolve():

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

    data=[list(map(int,input().split())) for i in range(M)]



    data1 = sorted(data, key=lambda x: x[1])

    cnt=[0]*N

    dic={}



    for [p,y] in data1:

        cnt[p-1]+=1

        dic[y]="%06d%06d"%(p,cnt[p-1])



    for [p,y] in data:

        print((dic[y]))













resolve()
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys

sys.setrecursionlimit(10**5 + 10)
# input = sys.stdin.readline
def resolve():
    N, M = list(map(int, input().split()))
    P = []
    city_count = [0] * N
    city_end = [1] * N
    for i in range(M):
        p, y = list(map(int, input().split()))
        city_count[p - 1] += 1
        P.append([p, y])
    P1 = sorted(P, key=lambda x: x[1])
    P1 = sorted(P1)
    for i in P1:
        i.append(city_end[i[0] - 1])
        city_end[i[0] - 1] += 1
    for i in P:
        print((str(i[0]).zfill(6) + str(i[2]).zfill(6)))
    # P = dict(sorted(P.items()))


resolve()

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys

sys.setrecursionlimit(10**5 + 10)
# input = sys.stdin.readline
def resolve():
    N, M = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(M)]
    data1 = sorted(data, key=lambda x: x[1])
    cnt = [0] * N
    dic = {}
    for [p, y] in data1:
        cnt[p - 1] += 1
        dic[y] = "%06d%06d" % (p, cnt[p - 1])
    for [p, y] in data:
        print((dic[y]))


resolve()

-    P = [] -    city_count = [0] * N -    city_end = [1] * N -    for i in range(M): -        p, y = list(map(int, input().split())) -        city_count[p - 1] += 1 -        P.append([p, y]) -    P1 = sorted(P, key=lambda x: x[1]) -    P1 = sorted(P1) -    for i in P1: -        i.append(city_end[i[0] - 1]) -        city_end[i[0] - 1] += 1 -    for i in P: -        print((str(i[0]).zfill(6) + str(i[2]).zfill(6))) -    # P = dict(sorted(P.items())) +    data = [list(map(int, input().split())) for i in range(M)] +    data1 = sorted(data, key=lambda x: x[1]) +    cnt = [0] * N +    dic = {} +    for [p, y] in data1: +        cnt[p - 1] += 1 +        dic[y] = "%06d%06d" % (p, cnt[p - 1]) +    for [p, y] in data: +        print((dic[y]))