def c_id():

    from collections import defaultdict

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

    City = [[s] + [int(i) for i in input().split()] for s in range(M)]



    # 同じ県に属する市を誕生年の早い順に並べ、順序付けする

    city_dict = defaultdict(list)

    for k, p, y in City:

        city_dict[p].append([k, p, y])

    for p in list(city_dict.keys()):

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

        for i in range(len(city_dict[p])):

            city_dict[p][i][2] = i + 1



    # 変換は終わった。通し番号順に並べる

    ans = sorted([e for v in list(city_dict.values()) for e in v])

    return '\n'.join(['{0:06d}{1:06d}'.format(p, num) for _, p, num in ans])  # 通し番号は不要



print((c_id()))
def c_id():

    from collections import defaultdict

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

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



    dic = defaultdict(list)

    # 県毎に市をまとめる

    for p, y in Cities:

        dic[p].append(y)

    # 市の認識番号を (座標) 圧縮

    for p, lst in list(dic.items()):

        dic[p] = {v: k for k, v in enumerate(sorted(lst), 1)}

    return '\n'.join(['{0:06d}{1:06d}'.format(p, dic[p][y]) for p, y in Cities])



print((c_id()))
def c_id():
    from collections import defaultdict

    N, M = list(map(int, input().split()))
    City = [[s] + [int(i) for i in input().split()] for s in range(M)]
    # 同じ県に属する市を誕生年の早い順に並べ、順序付けする
    city_dict = defaultdict(list)
    for k, p, y in City:
        city_dict[p].append([k, p, y])
    for p in list(city_dict.keys()):
        city_dict[p].sort(key=lambda x: x[2])
        for i in range(len(city_dict[p])):
            city_dict[p][i][2] = i + 1
    # 変換は終わった。通し番号順に並べる
    ans = sorted([e for v in list(city_dict.values()) for e in v])
    return "\n".join(["{0:06d}{1:06d}".format(p, num) for _, p, num in ans])  # 通し番号は不要


print((c_id()))

def c_id():
    from collections import defaultdict

    N, M = [int(i) for i in input().split()]
    Cities = [[int(i) for i in input().split()] for j in range(M)]
    dic = defaultdict(list)
    # 県毎に市をまとめる
    for p, y in Cities:
        dic[p].append(y)
    # 市の認識番号を (座標) 圧縮
    for p, lst in list(dic.items()):
        dic[p] = {v: k for k, v in enumerate(sorted(lst), 1)}
    return "\n".join(["{0:06d}{1:06d}".format(p, dic[p][y]) for p, y in Cities])


print((c_id()))

-    N, M = list(map(int, input().split())) -    City = [[s] + [int(i) for i in input().split()] for s in range(M)] -    # 同じ県に属する市を誕生年の早い順に並べ、順序付けする -    city_dict = defaultdict(list) -    for k, p, y in City: -        city_dict[p].append([k, p, y]) -    for p in list(city_dict.keys()): -        city_dict[p].sort(key=lambda x: x[2]) -        for i in range(len(city_dict[p])): -            city_dict[p][i][2] = i + 1 -    # 変換は終わった。通し番号順に並べる -    ans = sorted([e for v in list(city_dict.values()) for e in v]) -    return "\n".join(["{0:06d}{1:06d}".format(p, num) for _, p, num in ans])  # 通し番号は不要 +    N, M = [int(i) for i in input().split()] +    Cities = [[int(i) for i in input().split()] for j in range(M)] +    dic = defaultdict(list) +    # 県毎に市をまとめる +    for p, y in Cities: +        dic[p].append(y) +    # 市の認識番号を (座標) 圧縮 +    for p, lst in list(dic.items()): +        dic[p] = {v: k for k, v in enumerate(sorted(lst), 1)} +    return "\n".join(["{0:06d}{1:06d}".format(p, dic[p][y]) for p, y in Cities])