import itertools

import math

import fractions

import functools

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

py = []

for i in range(m):

    l = list(map(int, input().split()))

    l.append(i)

    py.append(l)



# py = [p,y,index]



# yでsort

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



prev = 0

py.sort(key=lambda x: x[0])

# py = [p, y, index, pの中でのindex]

for i in range(m):

    if prev != py[i][0]:

        prev = py[i][0]

        x = 1



    py[i].append(x)

    x += 1

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



p_i = ""

x_i = ""

for i in range(m):

    if(len(str(py[i][0])) == 6):

        p_i = str(py[i][0])

    if(len(str(py[i][0])) == 5):

        p_i = '0' + str(py[i][0])

    if(len(str(py[i][0])) == 4):

        p_i = '00'+str(py[i][0])

    if(len(str(py[i][0])) == 3):

        p_i = '000' + str(py[i][0])

    if(len(str(py[i][0])) == 2):

        p_i = '0000'+str(py[i][0])

    if(len(str(py[i][0])) == 1):

        p_i = '00000' + str(py[i][0])

    if(len(str(py[i][3])) == 6):

        x_i = str(py[i][3])

    if(len(str(py[i][3])) == 5):

        x_i = '0' + str(py[i][3])

    if(len(str(py[i][3])) == 4):

        x_i = '00'+str(py[i][3])

    if(len(str(py[i][3])) == 3):

        x_i = '000' + str(py[i][3])

    if(len(str(py[i][3])) == 2):

        x_i = '0000'+str(py[i][3])

    if(len(str(py[i][3])) == 1):

        x_i = '00000' + str(py[i][3])



    print((p_i + x_i))

import itertools

import math

import fractions

import functools

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

py = []

for i in range(m):

    l = list(map(int, input().split()))

    l.append(i)

    py.append(l)

 

# py = [p,y,index]

 

# yでsort

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



ans = [0] * (m)

ans1 = [0] * (m)

memo = {}

for item in py:

    ken = item[0]

    year = item[1]

    idx = item[2]

    ith = memo.get(ken, 1)

    ans[idx] = ith

    ans1[idx] = ken

    memo[ken] = ith + 1



for i in range(m):

    print((str(ans1[i]).zfill(6) + str(ans[i]).zfill(6)))

import itertools
import math
import fractions
import functools

n, m = list(map(int, input().split()))
py = []
for i in range(m):
    l = list(map(int, input().split()))
    l.append(i)
    py.append(l)
# py = [p,y,index]
# yでsort
py.sort(key=lambda x: x[1])
prev = 0
py.sort(key=lambda x: x[0])
# py = [p, y, index, pの中でのindex]
for i in range(m):
    if prev != py[i][0]:
        prev = py[i][0]
        x = 1
    py[i].append(x)
    x += 1
py.sort(key=lambda x: x[2])
p_i = ""
x_i = ""
for i in range(m):
    if len(str(py[i][0])) == 6:
        p_i = str(py[i][0])
    if len(str(py[i][0])) == 5:
        p_i = "0" + str(py[i][0])
    if len(str(py[i][0])) == 4:
        p_i = "00" + str(py[i][0])
    if len(str(py[i][0])) == 3:
        p_i = "000" + str(py[i][0])
    if len(str(py[i][0])) == 2:
        p_i = "0000" + str(py[i][0])
    if len(str(py[i][0])) == 1:
        p_i = "00000" + str(py[i][0])
    if len(str(py[i][3])) == 6:
        x_i = str(py[i][3])
    if len(str(py[i][3])) == 5:
        x_i = "0" + str(py[i][3])
    if len(str(py[i][3])) == 4:
        x_i = "00" + str(py[i][3])
    if len(str(py[i][3])) == 3:
        x_i = "000" + str(py[i][3])
    if len(str(py[i][3])) == 2:
        x_i = "0000" + str(py[i][3])
    if len(str(py[i][3])) == 1:
        x_i = "00000" + str(py[i][3])
    print((p_i + x_i))

import itertools
import math
import fractions
import functools

n, m = list(map(int, input().split()))
py = []
for i in range(m):
    l = list(map(int, input().split()))
    l.append(i)
    py.append(l)
# py = [p,y,index]
# yでsort
py.sort(key=lambda x: x[1])
ans = [0] * (m)
ans1 = [0] * (m)
memo = {}
for item in py:
    ken = item[0]
    year = item[1]
    idx = item[2]
    ith = memo.get(ken, 1)
    ans[idx] = ith
    ans1[idx] = ken
    memo[ken] = ith + 1
for i in range(m):
    print((str(ans1[i]).zfill(6) + str(ans[i]).zfill(6)))

-prev = 0 -py.sort(key=lambda x: x[0]) -# py = [p, y, index, pの中でのindex] +ans = [0] * (m) +ans1 = [0] * (m) +memo = {} +for item in py: +    ken = item[0] +    year = item[1] +    idx = item[2] +    ith = memo.get(ken, 1) +    ans[idx] = ith +    ans1[idx] = ken +    memo[ken] = ith + 1 -    if prev != py[i][0]: -        prev = py[i][0] -        x = 1 -    py[i].append(x) -    x += 1 -py.sort(key=lambda x: x[2]) -p_i = "" -x_i = "" -for i in range(m): -    if len(str(py[i][0])) == 6: -        p_i = str(py[i][0]) -    if len(str(py[i][0])) == 5: -        p_i = "0" + str(py[i][0]) -    if len(str(py[i][0])) == 4: -        p_i = "00" + str(py[i][0]) -    if len(str(py[i][0])) == 3: -        p_i = "000" + str(py[i][0]) -    if len(str(py[i][0])) == 2: -        p_i = "0000" + str(py[i][0]) -    if len(str(py[i][0])) == 1: -        p_i = "00000" + str(py[i][0]) -    if len(str(py[i][3])) == 6: -        x_i = str(py[i][3]) -    if len(str(py[i][3])) == 5: -        x_i = "0" + str(py[i][3]) -    if len(str(py[i][3])) == 4: -        x_i = "00" + str(py[i][3]) -    if len(str(py[i][3])) == 3: -        x_i = "000" + str(py[i][3]) -    if len(str(py[i][3])) == 2: -        x_i = "0000" + str(py[i][3]) -    if len(str(py[i][3])) == 1: -        x_i = "00000" + str(py[i][3]) -    print((p_i + x_i)) +    print((str(ans1[i]).zfill(6) + str(ans[i]).zfill(6)))