

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

arr = []

for i in range(m):

	ls = list(map(int,input().split()))+[i]

	arr.append(ls)



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



def st(a):

	b = list(str(a))

	while len(b) <= 5:

		b.insert(0,'0')

	c= ''.join(b)

	return c



dic = {}

for j in range(m):

	if arr[j][0] in dic:

		dic[arr[j][0]] += 1

		arr[j] += [dic[arr[j][0]]]

	else:

		dic[arr[j][0]] = 1

		arr[j] += [dic[arr[j][0]]]



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



for y in range(m):

	print(('{}{}'.format(st(arr[y][0]), st(arr[y][3]))))





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

arr = []

for i in range(m):

    arr += [list(map(int,input().split())) + [i]]  



dic = {}

for j in range(n+1):

    dic[j] = 1



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





for k in range(m):

    arr[k] += [dic[arr[k][0]]]

    dic[arr[k][0]] += 1



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

    

for v in range(m):

    print(("{:06d}{:06d}".format(arr[v][0],arr[v][3])))

    



n, m = list(map(int, input().split()))
arr = []
for i in range(m):
    ls = list(map(int, input().split())) + [i]
    arr.append(ls)
arr.sort(key=lambda x: x[1])


def st(a):
    b = list(str(a))
    while len(b) <= 5:
        b.insert(0, "0")
    c = "".join(b)
    return c


dic = {}
for j in range(m):
    if arr[j][0] in dic:
        dic[arr[j][0]] += 1
        arr[j] += [dic[arr[j][0]]]
    else:
        dic[arr[j][0]] = 1
        arr[j] += [dic[arr[j][0]]]
arr.sort(key=lambda x: x[2])
for y in range(m):
    print(("{}{}".format(st(arr[y][0]), st(arr[y][3]))))

n, m = list(map(int, input().split()))
arr = []
for i in range(m):
    arr += [list(map(int, input().split())) + [i]]
dic = {}
for j in range(n + 1):
    dic[j] = 1
arr.sort(key=lambda x: x[1])
for k in range(m):
    arr[k] += [dic[arr[k][0]]]
    dic[arr[k][0]] += 1
arr.sort(key=lambda x: x[2])
for v in range(m):
    print(("{:06d}{:06d}".format(arr[v][0], arr[v][3])))

-    ls = list(map(int, input().split())) + [i] -    arr.append(ls) +    arr += [list(map(int, input().split())) + [i]] +dic = {} +for j in range(n + 1): +    dic[j] = 1 - - -def st(a): -    b = list(str(a)) -    while len(b) <= 5: -        b.insert(0, "0") -    c = "".join(b) -    return c - - -dic = {} -for j in range(m): -    if arr[j][0] in dic: -        dic[arr[j][0]] += 1 -        arr[j] += [dic[arr[j][0]]] -    else: -        dic[arr[j][0]] = 1 -        arr[j] += [dic[arr[j][0]]] +for k in range(m): +    arr[k] += [dic[arr[k][0]]] +    dic[arr[k][0]] += 1 -for y in range(m): -    print(("{}{}".format(st(arr[y][0]), st(arr[y][3])))) +for v in range(m): +    print(("{:06d}{:06d}".format(arr[v][0], arr[v][3])))