# http://drken1215.hatenablog.com/entry/2019/03/21/234900

# 写経



from bisect import bisect_left



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

PY = []

e = [[] for _ in range(n + 1)]

for _ in range(m):

    _p, _y = list(map(int, input().split()))

    e[_p].append(_y)

    PY.append((_p, _y))



for idx in range(n + 1):

    e[idx] = tuple(sorted(set(e[idx])))



for p, y in PY:

    id = bisect_left(e[p], y)

    print(('{:06d}{:06d}'.format(p, id + 1)))

# http://drken1215.hatenablog.com/entry/2019/03/21/234900

# 写経



def main():

    from bisect import bisect_left

    import sys



    input = sys.stdin.readline



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

    PY = []

    e = [[] for _ in range(n + 1)]

    for _ in range(m):

        _p, _y = list(map(int, input().split()))

        e[_p].append(_y)

        PY.append((_p, _y))



    for idx in range(n + 1):

        e[idx] = tuple(sorted(set(e[idx])))



    for p, y in PY:

        id = bisect_left(e[p], y)

        print(('{:06d}{:06d}'.format(p, id + 1)))





if __name__ == '__main__':

    main()

# http://drken1215.hatenablog.com/entry/2019/03/21/234900
# 写経
from bisect import bisect_left

n, m = list(map(int, input().split()))
PY = []
e = [[] for _ in range(n + 1)]
for _ in range(m):
    _p, _y = list(map(int, input().split()))
    e[_p].append(_y)
    PY.append((_p, _y))
for idx in range(n + 1):
    e[idx] = tuple(sorted(set(e[idx])))
for p, y in PY:
    id = bisect_left(e[p], y)
    print(("{:06d}{:06d}".format(p, id + 1)))

# http://drken1215.hatenablog.com/entry/2019/03/21/234900
# 写経
def main():
    from bisect import bisect_left
    import sys

    input = sys.stdin.readline
    n, m = list(map(int, input().split()))
    PY = []
    e = [[] for _ in range(n + 1)]
    for _ in range(m):
        _p, _y = list(map(int, input().split()))
        e[_p].append(_y)
        PY.append((_p, _y))
    for idx in range(n + 1):
        e[idx] = tuple(sorted(set(e[idx])))
    for p, y in PY:
        id = bisect_left(e[p], y)
        print(("{:06d}{:06d}".format(p, id + 1)))


if __name__ == "__main__":
    main()

-from bisect import bisect_left +def main(): +    from bisect import bisect_left +    import sys -n, m = list(map(int, input().split())) -PY = [] -e = [[] for _ in range(n + 1)] -for _ in range(m): -    _p, _y = list(map(int, input().split())) -    e[_p].append(_y) -    PY.append((_p, _y)) -for idx in range(n + 1): -    e[idx] = tuple(sorted(set(e[idx]))) -for p, y in PY: -    id = bisect_left(e[p], y) -    print(("{:06d}{:06d}".format(p, id + 1))) +    input = sys.stdin.readline +    n, m = list(map(int, input().split())) +    PY = [] +    e = [[] for _ in range(n + 1)] +    for _ in range(m): +        _p, _y = list(map(int, input().split())) +        e[_p].append(_y) +        PY.append((_p, _y)) +    for idx in range(n + 1): +        e[idx] = tuple(sorted(set(e[idx]))) +    for p, y in PY: +        id = bisect_left(e[p], y) +        print(("{:06d}{:06d}".format(p, id + 1))) + + +if __name__ == "__main__": +    main()