# -*- coding: utf-8 -*-



class City:

    def __init__(self, id, pref, year):

        self.id = id

        self.pref = pref

        self.year = year

        self.num = 0



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

cities = []

for i in range(M):

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

    cities.append(City(i+1, p, y))



cities.sort(key=lambda city: city.year)



p_cnt = [0] * N

for i in range(M):

    # 0埋め

    pref_num = str(cities[i].pref).zfill(6)

    p_cnt[cities[i].pref-1] += 1

    city_num = str(p_cnt[cities[i].pref-1]).zfill(6)

    cities[i].num = pref_num + city_num



cities.sort(key=lambda city: city.id)



for i in range(M):

    print((cities[i].num))
# -*- coding: utf-8 -*-



import sys



def input(): return sys.stdin.readline().strip()

def list2d(a, b, c): return [[c] * b for i in range(a)]

def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1): return int(-(-x // y))

def INT(): return int(eval(input()))

def MAP(): return list(map(int, input().split()))

def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes(): print('Yes')

def No(): print('No')

def YES(): print('YES')

def NO(): print('NO')

sys.setrecursionlimit(10 ** 9)

INF = 10 ** 18

MOD = 10 ** 9 + 7



N, M = MAP()

YPC = []

for c in range(M):

    p, y = MAP()

    p -= 1

    YPC.append((y, p, c))



YPC.sort()

ans = [()] * M

pcnt = [0] * N

for _, p, c in YPC:

    ans[c] = (p + 1, pcnt[p] + 1)

    pcnt[p] += 1



for p, c in ans:

    print((str(p).zfill(6) + str(c).zfill(6)))

# -*- coding: utf-8 -*-
class City:
    def __init__(self, id, pref, year):
        self.id = id
        self.pref = pref
        self.year = year
        self.num = 0


N, M = list(map(int, input().split()))
cities = []
for i in range(M):
    p, y = list(map(int, input().split()))
    cities.append(City(i + 1, p, y))
cities.sort(key=lambda city: city.year)
p_cnt = [0] * N
for i in range(M):
    # 0埋め
    pref_num = str(cities[i].pref).zfill(6)
    p_cnt[cities[i].pref - 1] += 1
    city_num = str(p_cnt[cities[i].pref - 1]).zfill(6)
    cities[i].num = pref_num + city_num
cities.sort(key=lambda city: city.id)
for i in range(M):
    print((cities[i].num))

# -*- coding: utf-8 -*-
import sys


def input():
    return sys.stdin.readline().strip()


def list2d(a, b, c):
    return [[c] * b for i in range(a)]


def list3d(a, b, c, d):
    return [[[d] * c for j in range(b)] for i in range(a)]


def list4d(a, b, c, d, e):
    return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]


def ceil(x, y=1):
    return int(-(-x // y))


def INT():
    return int(eval(input()))


def MAP():
    return list(map(int, input().split()))


def LIST(N=None):
    return list(MAP()) if N is None else [INT() for i in range(N)]


def Yes():
    print("Yes")


def No():
    print("No")


def YES():
    print("YES")


def NO():
    print("NO")


sys.setrecursionlimit(10**9)
INF = 10**18
MOD = 10**9 + 7
N, M = MAP()
YPC = []
for c in range(M):
    p, y = MAP()
    p -= 1
    YPC.append((y, p, c))
YPC.sort()
ans = [()] * M
pcnt = [0] * N
for _, p, c in YPC:
    ans[c] = (p + 1, pcnt[p] + 1)
    pcnt[p] += 1
for p, c in ans:
    print((str(p).zfill(6) + str(c).zfill(6)))

-class City: -    def __init__(self, id, pref, year): -        self.id = id -        self.pref = pref -        self.year = year -        self.num = 0 +import sys -N, M = list(map(int, input().split())) -cities = [] -for i in range(M): -    p, y = list(map(int, input().split())) -    cities.append(City(i + 1, p, y)) -cities.sort(key=lambda city: city.year) -p_cnt = [0] * N -for i in range(M): -    # 0埋め -    pref_num = str(cities[i].pref).zfill(6) -    p_cnt[cities[i].pref - 1] += 1 -    city_num = str(p_cnt[cities[i].pref - 1]).zfill(6) -    cities[i].num = pref_num + city_num -cities.sort(key=lambda city: city.id) -for i in range(M): -    print((cities[i].num)) +def input(): +    return sys.stdin.readline().strip() + + +def list2d(a, b, c): +    return [[c] * b for i in range(a)] + + +def list3d(a, b, c, d): +    return [[[d] * c for j in range(b)] for i in range(a)] + + +def list4d(a, b, c, d, e): +    return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)] + + +def ceil(x, y=1): +    return int(-(-x // y)) + + +def INT(): +    return int(eval(input())) + + +def MAP(): +    return list(map(int, input().split())) + + +def LIST(N=None): +    return list(MAP()) if N is None else [INT() for i in range(N)] + + +def Yes(): +    print("Yes") + + +def No(): +    print("No") + + +def YES(): +    print("YES") + + +def NO(): +    print("NO") + + +sys.setrecursionlimit(10**9) +INF = 10**18 +MOD = 10**9 + 7 +N, M = MAP() +YPC = [] +for c in range(M): +    p, y = MAP() +    p -= 1 +    YPC.append((y, p, c)) +YPC.sort() +ans = [()] * M +pcnt = [0] * N +for _, p, c in YPC: +    ans[c] = (p + 1, pcnt[p] + 1) +    pcnt[p] += 1 +for p, c in ans: +    print((str(p).zfill(6) + str(c).zfill(6)))