Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N, M = map(int, input().split())

cities_prefec = {}
pref_ids = []
years = []

for i in range(M):
    prefec_id, year = map(int, input().split())

    pref_ids.append(prefec_id)
    years.append(year)

    if prefec_id in cities_prefec:
        bisect.insort(cities_prefec[prefec_id], year)
    else:
        cities_prefec[prefec_id] = [year]

for i in range(M):
    p_id = pref_ids[i]
    cn = bisect.bisect_left(cities_prefec[p_id], years[i]) + 1
    print("{0:0>6}{1:0>6}".format(p_id, cn))


Fixed submission:
if __name__ == "__main__":
    _, M = map(int, input().split())
    
    outputs = [0 for _ in range(M)]
    cities = {}

    for i in range(M):
        pref, year = map(int, input().split())
        
        if pref not in cities:
            cities[pref] = {}

        cities[pref][year] = i

    for p in cities:
        city_years = list(cities[p].keys())
        city_years.sort()

        for i, cy in enumerate(city_years):
            outputs[cities[p][cy]] = "{:06}{:06}".format(p, i + 1)

    for line in outputs:
        print(line)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N, M = map(int, input().split())

cities_prefec = {}
data = []
cities = []
years = []

for i in range(M):
    prefec_id, year = map(int, input().split())

    data.append(
        {
            "pref_id": prefec_id,
            "year": year
        }
    )

    if prefec_id in cities_prefec:
        bisect.insort(cities_prefec[prefec_id], year)
    else:
        cities_prefec[prefec_id] = [year]


for d in data:
    p_id = d["pref_id"]
    cn = bisect.bisect_left(cities_prefec[p_id], d["year"]) + 1
    print("{0:0>6}{1:0>6}".format(p_id, cn))


Fixed submission:
if __name__ == "__main__":
    _, M = map(int, input().split())
    
    outputs = [0 for _ in range(M)]
    cities = {}

    for i in range(M):
        pref, year = map(int, input().split())
        
        if pref not in cities:
            cities[pref] = {}

        cities[pref][year] = i

    for p in cities:
        city_years = list(cities[p].keys())
        city_years.sort()

        for i, cy in enumerate(city_years):
            outputs[cities[p][cy]] = "{:06}{:06}".format(p, i + 1)

    for line in outputs:
        print(line)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N, M = map(int, input().split())

cities_prefec = {}
data = []
cities = []
years = []

for i in range(M):
    prefec_id, year = map(int, input().split())

    data.append(
        {
            "pref_id": prefec_id,
            "year": year
        }
    )

    if prefec_id in cities_prefec:
        bisect.insort(cities_prefec[prefec_id], year)
    else:
        cities_prefec[prefec_id] = [year]


for d in data:
    p_id = d["pref_id"]
    cn = bisect.bisect_left(cities_prefec[p_id], d["year"]) + 1
    print("{p_id:0>6}{cn:0>6}".format(**locals()))


Fixed submission:
if __name__ == "__main__":
    _, M = map(int, input().split())
    
    outputs = [0 for _ in range(M)]
    cities = {}

    for i in range(M):
        pref, year = map(int, input().split())
        
        if pref not in cities:
            cities[pref] = {}

        cities[pref][year] = i

    for p in cities:
        city_years = list(cities[p].keys())
        city_years.sort()

        for i, cy in enumerate(city_years):
            outputs[cities[p][cy]] = "{:06}{:06}".format(p, i + 1)

    for line in outputs:
        print(line)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N, M = map(int, input().split())

cities_prefec = {}
data = []
cities = []
years = []

for i in range(M):
    prefec_id, year = map(int, input().split())

    data.append(
        {
            "pref_id": prefec_id,
            "year": year
        }
    )

    if prefec_id in cities_prefec:
        bisect.insort(cities_prefec[prefec_id], year)
    else:
        cities_prefec[prefec_id] = [year]


for d in data:
    p_id = d["pref_id"]
    cn = cities_prefec[p_id].index(d["year"]) + 1
    print("{p_id:0>6}{cn:0>6}".format(**locals()))


Fixed submission:
if __name__ == "__main__":
    _, M = map(int, input().split())
    
    outputs = [0 for _ in range(M)]
    cities = {}

    for i in range(M):
        pref, year = map(int, input().split())
        
        if pref not in cities:
            cities[pref] = {}

        cities[pref][year] = i

    for p in cities:
        city_years = list(cities[p].keys())
        city_years.sort()

        for i, cy in enumerate(city_years):
            outputs[cities[p][cy]] = "{:06}{:06}".format(p, i + 1)

    for line in outputs:
        print(line)