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

P = []

Y = []

for i in range(M):

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

    P.append(p)

    Y.append(y)





pref_map = {}

for i in range(1, N+1):

    pref_map[i] = []



for i in range(M):

    pref_map[P[i]].append([i, Y[i]])





city_list = []

for k in list(pref_map.keys()):

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

    idx = 1

    for c in pref_map[k]:

        city_list.append([c[0], k, idx])

        idx += 1



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



for city in city_list:

    print((format(city[1], '06d') + format(city[2], '06d')))
import bisect

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

py_list = [list(map(int, input().split())) for i in range(M)]



pref_city_map = {}



for i in range(N+1):

    pref_city_map[i] = []



for py in py_list:

    p = py[0]

    pref_city_map[p].append(py[1])



for k in list(pref_city_map.keys()):

    pref_city_map[k].sort()



for py in py_list:

    p = py[0]

    y = py[1]

    p_str = str(p).zfill(6)

    idx = bisect.bisect(pref_city_map[p], y)

    idx_str  = str(idx).zfill(6)

    print((p_str + idx_str))





N, M = list(map(int, input().split()))
P = []
Y = []
for i in range(M):
    p, y = list(map(int, input().split()))
    P.append(p)
    Y.append(y)
pref_map = {}
for i in range(1, N + 1):
    pref_map[i] = []
for i in range(M):
    pref_map[P[i]].append([i, Y[i]])
city_list = []
for k in list(pref_map.keys()):
    pref_map[k].sort(key=lambda x: x[1])
    idx = 1
    for c in pref_map[k]:
        city_list.append([c[0], k, idx])
        idx += 1
city_list.sort(key=lambda x: x[0])
for city in city_list:
    print((format(city[1], "06d") + format(city[2], "06d")))

import bisect

N, M = list(map(int, input().split()))
py_list = [list(map(int, input().split())) for i in range(M)]
pref_city_map = {}
for i in range(N + 1):
    pref_city_map[i] = []
for py in py_list:
    p = py[0]
    pref_city_map[p].append(py[1])
for k in list(pref_city_map.keys()):
    pref_city_map[k].sort()
for py in py_list:
    p = py[0]
    y = py[1]
    p_str = str(p).zfill(6)
    idx = bisect.bisect(pref_city_map[p], y)
    idx_str = str(idx).zfill(6)
    print((p_str + idx_str))

+import bisect + -P = [] -Y = [] -for i in range(M): -    p, y = list(map(int, input().split())) -    P.append(p) -    Y.append(y) -pref_map = {} -for i in range(1, N + 1): -    pref_map[i] = [] -for i in range(M): -    pref_map[P[i]].append([i, Y[i]]) -city_list = [] -for k in list(pref_map.keys()): -    pref_map[k].sort(key=lambda x: x[1]) -    idx = 1 -    for c in pref_map[k]: -        city_list.append([c[0], k, idx]) -        idx += 1 -city_list.sort(key=lambda x: x[0]) -for city in city_list: -    print((format(city[1], "06d") + format(city[2], "06d"))) +py_list = [list(map(int, input().split())) for i in range(M)] +pref_city_map = {} +for i in range(N + 1): +    pref_city_map[i] = [] +for py in py_list: +    p = py[0] +    pref_city_map[p].append(py[1]) +for k in list(pref_city_map.keys()): +    pref_city_map[k].sort() +for py in py_list: +    p = py[0] +    y = py[1] +    p_str = str(p).zfill(6) +    idx = bisect.bisect(pref_city_map[p], y) +    idx_str = str(idx).zfill(6) +    print((p_str + idx_str))