Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter 
n,m = map(int,input().split())
list1 = []
#[input番号,県番号,年,県における順番]
for i in range(m):
    list1.append([i+1] + list(map(int,input().split())))
list1.sort(key=itemgetter(1,2))
list1[0].append(0)
for i in range(1,m):
    if list1[i-1][1] == list1[i][1]:
        list1[i].append(list1[i-1][3]+1)
    else:
        list1[i].append(0)
for i in range(m):
    list1.sort(key=itemgetter(0))

#int型
def zeropadding(s):
    padding = 6 #何桁揃えにするか入力
    return ("{0:0"+str(padding)+"d}").format(s)
    #returnはstr型なので注意！

for i in range(m):
    print(zeropadding(list1[i][1])+zeropadding(list1[i][3]+1))


Fixed submission:
from copy import deepcopy as dp
from operator import itemgetter as ig
n,m = map(int,input().split())
#[input番号,県番号,年,県における順番]
list1 = []
for i in range(m):
    list1.append([i] + list(map(int,input().split())))

list2 = dp(list1)
list2.sort(key=ig(1,2))
city_number = 0
list2[0].append(city_number)
for i in range(1,m):
    if list2[i][1] == list2[i-1][1]:
        city_number += 1
        list2[i].append(city_number)
    else:
        city_number = 0
        list2[i].append(city_number)
list2.sort(key=ig(0))
for i in range(m):
    print("{0:06d}".format(list2[i][1])+"{0:06d}".format(list2[i][3]+1))

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
list1 = [list(map(int,input().split())) for i in range(m)]

list2 = [[] for i in range(n)]
#int型
def zeropadding(s):
    padding = 6 #何桁揃えにするか入力
    return ("{0:0"+str(padding)+"d}").format(s)
    #returnはstr型なので注意！

for i in range(m):
    list2[list1[i][0]-1].append(list1[i][1])
for i in range(n):
    list2[i].sort()

for i in range(m):
    print(zeropadding(list1[i][0])+zeropadding(list2[list1[i][0]-1].index(list1[i][1])+1))

Fixed submission:
from copy import deepcopy as dp
from operator import itemgetter as ig
n,m = map(int,input().split())
#[input番号,県番号,年,県における順番]
list1 = []
for i in range(m):
    list1.append([i] + list(map(int,input().split())))

list2 = dp(list1)
list2.sort(key=ig(1,2))
city_number = 0
list2[0].append(city_number)
for i in range(1,m):
    if list2[i][1] == list2[i-1][1]:
        city_number += 1
        list2[i].append(city_number)
    else:
        city_number = 0
        list2[i].append(city_number)
list2.sort(key=ig(0))
for i in range(m):
    print("{0:06d}".format(list2[i][1])+"{0:06d}".format(list2[i][3]+1))

Buggy python submission (verdict: Time Limit Exceeded):
import copy
n,m = map(int,input().split())
list1 = [list(map(int,input().split())) for i in range(m)]

list2 = copy.deepcopy(list1)
#int型
def zeropadding(s):
    padding = 6 #何桁揃えにするか入力
    return ("{0:0"+str(padding)+"d}").format(s)
    #returnはstr型なので注意！

#空の多次元リスト
list3 = [[] for i in range(n+1)]

list2.sort()

for i in range(m):
    list3[list2[i][0]].append(list2[i][1])

for i in range(m):
    print(zeropadding(list1[i][0])+zeropadding(list3[list1[i][0]].index(list1[i][1])+1))


Fixed submission:
from copy import deepcopy as dp
from operator import itemgetter as ig
n,m = map(int,input().split())
#[input番号,県番号,年,県における順番]
list1 = []
for i in range(m):
    list1.append([i] + list(map(int,input().split())))

list2 = dp(list1)
list2.sort(key=ig(1,2))
city_number = 0
list2[0].append(city_number)
for i in range(1,m):
    if list2[i][1] == list2[i-1][1]:
        city_number += 1
        list2[i].append(city_number)
    else:
        city_number = 0
        list2[i].append(city_number)
list2.sort(key=ig(0))
for i in range(m):
    print("{0:06d}".format(list2[i][1])+"{0:06d}".format(list2[i][3]+1))