import sys



input = sys.stdin.readline



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



Pm = [0] * M

Ym = [0] * M

ym = [0] * M



Am = [[0 for i in range(2)] for j in range(M)]

Cn = [0] * N



D = {}



for i in range(M):

    P, Y = list(map(int, input().split()))



    Pm[i], Ym[i] = P, Y



    ym[i] = Y



    D[Y] = i



ym.sort()



for i in range(M):

    k = D[ym[i]]



    # 0-indexed

    Cn[Pm[k] - 1] += 1

    Am[k] = [Pm[k], Cn[Pm[k] - 1]]



for i in range(M):

    print(('{:06d}{:06d}'.format(Am[i][0], Am[i][1])))

def main():

    N, M, *PY = list(map(int, open(0).read().split()))

    lst = []

    ans = [""] * M

    for k, py in enumerate(zip(*[iter(PY)] * 2)):

        lst.append((py[0], py[1], k))

    lst.sort()

    pre, num = lst[0][0], 1

    for cur, y, i in lst:

        if pre != cur:

            num = 1

        ans[i] = "{:06}{:06}".format(cur, num)

        num += 1

        pre = cur

    print(("\n".join(ans)))

    return





main()

import sys

input = sys.stdin.readline
N, M = list(map(int, input().split()))
Pm = [0] * M
Ym = [0] * M
ym = [0] * M
Am = [[0 for i in range(2)] for j in range(M)]
Cn = [0] * N
D = {}
for i in range(M):
    P, Y = list(map(int, input().split()))
    Pm[i], Ym[i] = P, Y
    ym[i] = Y
    D[Y] = i
ym.sort()
for i in range(M):
    k = D[ym[i]]
    # 0-indexed
    Cn[Pm[k] - 1] += 1
    Am[k] = [Pm[k], Cn[Pm[k] - 1]]
for i in range(M):
    print(("{:06d}{:06d}".format(Am[i][0], Am[i][1])))

def main():
    N, M, *PY = list(map(int, open(0).read().split()))
    lst = []
    ans = [""] * M
    for k, py in enumerate(zip(*[iter(PY)] * 2)):
        lst.append((py[0], py[1], k))
    lst.sort()
    pre, num = lst[0][0], 1
    for cur, y, i in lst:
        if pre != cur:
            num = 1
        ans[i] = "{:06}{:06}".format(cur, num)
        num += 1
        pre = cur
    print(("\n".join(ans)))
    return


main()

-import sys +def main(): +    N, M, *PY = list(map(int, open(0).read().split())) +    lst = [] +    ans = [""] * M +    for k, py in enumerate(zip(*[iter(PY)] * 2)): +        lst.append((py[0], py[1], k)) +    lst.sort() +    pre, num = lst[0][0], 1 +    for cur, y, i in lst: +        if pre != cur: +            num = 1 +        ans[i] = "{:06}{:06}".format(cur, num) +        num += 1 +        pre = cur +    print(("\n".join(ans))) +    return -input = sys.stdin.readline -N, M = list(map(int, input().split())) -Pm = [0] * M -Ym = [0] * M -ym = [0] * M -Am = [[0 for i in range(2)] for j in range(M)] -Cn = [0] * N -D = {} -for i in range(M): -    P, Y = list(map(int, input().split())) -    Pm[i], Ym[i] = P, Y -    ym[i] = Y -    D[Y] = i -ym.sort() -for i in range(M): -    k = D[ym[i]] -    # 0-indexed -    Cn[Pm[k] - 1] += 1 -    Am[k] = [Pm[k], Cn[Pm[k] - 1]] -for i in range(M): -    print(("{:06d}{:06d}".format(Am[i][0], Am[i][1]))) + +main()