n, m = (int(i) for i in input().split())

py = [[int(i) for i in input().split()] for j in range(m)]

pre = {}

for i in range(m):

    cur_p = py[i][0]

    cur_p_cities = pre.get(cur_p,[])

    cur_p_cities.append(i)

    pre[cur_p] = cur_p_cities



for i in list(pre.keys()):

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

    city_order = tuple(range(1,len(pre[i])+1))

    pre[i] = dict(list(zip(pre[i],city_order)))



city_nums = []

for i in range(m):

    p = py[i][0]

    x = pre[py[i][0]][i]

    ans = "{:0>6d}".format(p)+"{:0>6d}".format(x)

    city_nums.append(ans)

    

for c_n in city_nums:

    print(c_n)
def main():

    N, M = (int(i) for i in input().split())

    PY = [([int(i) for i in input().split()], j) for j in range(M)]

    dic = {i: [] for i in range(N)}  # 県iの市を生まれた順に持つ

    A = sorted(PY, key=lambda p: p[0][1])

    for py, i in A:

        dic[py[0]-1].append(i)



    ans = []

    for p in range(N):  # 県ごとに番号を振る

        for x, i in enumerate(dic[p], start=1):

            # 県pの中でx番目に生まれた市i

            upper = "{:>06}".format(str(PY[i][0][0]))

            lower = "{:>06}".format(str(x))

            ans.append((upper+lower, i))

    ans.sort(key=lambda p: p[1])

    for a, _ in ans:

        print(a)





if __name__ == '__main__':

    main()

n, m = (int(i) for i in input().split())
py = [[int(i) for i in input().split()] for j in range(m)]
pre = {}
for i in range(m):
    cur_p = py[i][0]
    cur_p_cities = pre.get(cur_p, [])
    cur_p_cities.append(i)
    pre[cur_p] = cur_p_cities
for i in list(pre.keys()):
    pre[i].sort(key=lambda x: py[x][1])
    city_order = tuple(range(1, len(pre[i]) + 1))
    pre[i] = dict(list(zip(pre[i], city_order)))
city_nums = []
for i in range(m):
    p = py[i][0]
    x = pre[py[i][0]][i]
    ans = "{:0>6d}".format(p) + "{:0>6d}".format(x)
    city_nums.append(ans)
for c_n in city_nums:
    print(c_n)

def main():
    N, M = (int(i) for i in input().split())
    PY = [([int(i) for i in input().split()], j) for j in range(M)]
    dic = {i: [] for i in range(N)}  # 県iの市を生まれた順に持つ
    A = sorted(PY, key=lambda p: p[0][1])
    for py, i in A:
        dic[py[0] - 1].append(i)
    ans = []
    for p in range(N):  # 県ごとに番号を振る
        for x, i in enumerate(dic[p], start=1):
            # 県pの中でx番目に生まれた市i
            upper = "{:>06}".format(str(PY[i][0][0]))
            lower = "{:>06}".format(str(x))
            ans.append((upper + lower, i))
    ans.sort(key=lambda p: p[1])
    for a, _ in ans:
        print(a)


if __name__ == "__main__":
    main()

-n, m = (int(i) for i in input().split()) -py = [[int(i) for i in input().split()] for j in range(m)] -pre = {} -for i in range(m): -    cur_p = py[i][0] -    cur_p_cities = pre.get(cur_p, []) -    cur_p_cities.append(i) -    pre[cur_p] = cur_p_cities -for i in list(pre.keys()): -    pre[i].sort(key=lambda x: py[x][1]) -    city_order = tuple(range(1, len(pre[i]) + 1)) -    pre[i] = dict(list(zip(pre[i], city_order))) -city_nums = [] -for i in range(m): -    p = py[i][0] -    x = pre[py[i][0]][i] -    ans = "{:0>6d}".format(p) + "{:0>6d}".format(x) -    city_nums.append(ans) -for c_n in city_nums: -    print(c_n) +def main(): +    N, M = (int(i) for i in input().split()) +    PY = [([int(i) for i in input().split()], j) for j in range(M)] +    dic = {i: [] for i in range(N)}  # 県iの市を生まれた順に持つ +    A = sorted(PY, key=lambda p: p[0][1]) +    for py, i in A: +        dic[py[0] - 1].append(i) +    ans = [] +    for p in range(N):  # 県ごとに番号を振る +        for x, i in enumerate(dic[p], start=1): +            # 県pの中でx番目に生まれた市i +            upper = "{:>06}".format(str(PY[i][0][0])) +            lower = "{:>06}".format(str(x)) +            ans.append((upper + lower, i)) +    ans.sort(key=lambda p: p[1]) +    for a, _ in ans: +        print(a) + + +if __name__ == "__main__": +    main()