import sys

input = sys.stdin.readline



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

ans = [""] * m

arr = []

cnt = 1

for i in range(m):

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

    arr.append((p, y, i))

arr.sort()



ans[arr[0][2]] = "{:06}{:06}".format(arr[0][0], cnt)

for i in range(1, m):

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

        cnt += 1

    else:

        cnt = 1

    ans[arr[i][2]] = "{:06}{:06}".format(arr[i][0], cnt)



for i in ans:

    print(i)
## ABC113C - ID

import sys

input = sys.stdin.readline



def main():

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

    ans = [""] * m

    arr = []

    cnt = 1

    for i in range(m):

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

        arr += [(p, y, i)]

    arr = sorted(arr)



    ans[arr[0][2]] = "{:06}{:06}".format(arr[0][0], cnt)

    for i in range(1, m):

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

            cnt += 1

        else:

            cnt = 1

        ans[arr[i][2]] = "{:06}{:06}".format(arr[i][0], cnt)



    for i in ans:

        print(i)





if __name__ == "__main__":

    main()
import sys

input = sys.stdin.readline
n, m = list(map(int, input().split()))
ans = [""] * m
arr = []
cnt = 1
for i in range(m):
    p, y = list(map(int, input().split()))
    arr.append((p, y, i))
arr.sort()
ans[arr[0][2]] = "{:06}{:06}".format(arr[0][0], cnt)
for i in range(1, m):
    if arr[i - 1][0] == arr[i][0]:
        cnt += 1
    else:
        cnt = 1
    ans[arr[i][2]] = "{:06}{:06}".format(arr[i][0], cnt)
for i in ans:
    print(i)

## ABC113C - ID
import sys

input = sys.stdin.readline


def main():
    n, m = list(map(int, input().rstrip().split()))
    ans = [""] * m
    arr = []
    cnt = 1
    for i in range(m):
        p, y = list(map(int, input().split()))
        arr += [(p, y, i)]
    arr = sorted(arr)
    ans[arr[0][2]] = "{:06}{:06}".format(arr[0][0], cnt)
    for i in range(1, m):
        if arr[i - 1][0] == arr[i][0]:
            cnt += 1
        else:
            cnt = 1
        ans[arr[i][2]] = "{:06}{:06}".format(arr[i][0], cnt)
    for i in ans:
        print(i)


if __name__ == "__main__":
    main()

+## ABC113C - ID -n, m = list(map(int, input().split())) -ans = [""] * m -arr = [] -cnt = 1 -for i in range(m): -    p, y = list(map(int, input().split())) -    arr.append((p, y, i)) -arr.sort() -ans[arr[0][2]] = "{:06}{:06}".format(arr[0][0], cnt) -for i in range(1, m): -    if arr[i - 1][0] == arr[i][0]: -        cnt += 1 -    else: -        cnt = 1 -    ans[arr[i][2]] = "{:06}{:06}".format(arr[i][0], cnt) -for i in ans: -    print(i) + + +def main(): +    n, m = list(map(int, input().rstrip().split())) +    ans = [""] * m +    arr = [] +    cnt = 1 +    for i in range(m): +        p, y = list(map(int, input().split())) +        arr += [(p, y, i)] +    arr = sorted(arr) +    ans[arr[0][2]] = "{:06}{:06}".format(arr[0][0], cnt) +    for i in range(1, m): +        if arr[i - 1][0] == arr[i][0]: +            cnt += 1 +        else: +            cnt = 1 +        ans[arr[i][2]] = "{:06}{:06}".format(arr[i][0], cnt) +    for i in ans: +        print(i) + + +if __name__ == "__main__": +    main()