Buggy python submission (verdict: Runtime Error):
"""
import numpy as np
N, M = map(int, input().split())
cities = {}
Y = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = p
    Y[i] = y

ans = {}
sorted_Y = sorted(Y.items(), key=lambda x:x[1])
P_i = np.zeros(N)
for i,y in sorted_Y:
    p = cities[i]
    P_i[p-1] += 1
    ans[i] = (p, int(P_i[p-1]))

for i in range(M):
    print('{0:06}{1:06}'.format(ans[i][0], ans[i][1]))
"""

n, m = map(int,input().split())
pys = []
for i in range(m):
    x = map(int, input().split())
    x = [x[0],x[1],i]
    pys.append(x)

pys.sort()
pp = -1
lid = 0
ans = []
for i in range(m):
    if pp == pys[i][0]:
        lid += 1
    else:
        lid = 1
        pp = pys[i][0]
    ans.append(pp*10**6+lid)

for v in ans:
    print(':012d'.format(v))


Fixed submission:
import numpy as np
N, M = map(int, input().split())
cities = {}
P = {}
Y = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = p
    Y[i] = y

ans = {}
sorted_Y = sorted(Y.items(), key=lambda x:x[1])
P_i = np.zeros(N)
for i,y in sorted_Y:
    p = cities[i]
    P_i[p-1] += 1
    ans[i] = (p, int(P_i[p-1]))

for i in range(M):
    print('{0:06}{1:06}'.format(ans[i][0], ans[i][1]))

Buggy python submission (verdict: Runtime Error):
import numpy as np
N, M = map(int, input().split())
cities = {}
P = {}
Y = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = p
    Y[i] = y

ans = []
sorted_Y = sorted(Y.items(), key=lambda x:x[1])
P_i = np.zeros(N)
for i,y in sorted_Y:
    p = cities[i]
    P_i[p] += 1
    ans.append(p,P_i[p])

for p,x in ans:
    print('{0:06}{1:06}'.format(p, x))


Fixed submission:
import numpy as np
N, M = map(int, input().split())
cities = {}
P = {}
Y = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = p
    Y[i] = y

ans = {}
sorted_Y = sorted(Y.items(), key=lambda x:x[1])
P_i = np.zeros(N)
for i,y in sorted_Y:
    p = cities[i]
    P_i[p-1] += 1
    ans[i] = (p, int(P_i[p-1]))

for i in range(M):
    print('{0:06}{1:06}'.format(ans[i][0], ans[i][1]))

Buggy python submission (verdict: Runtime Error):
import numpy as np
N, M = map(int, input().split())
cities = {}
P = {}
Y = []
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = (p,y)
    Y.append(y)

sorted_Y = sorted(Y)
sorted_P = {p:sorted(P[p].items(), key=lambda x:x[1]) for p in P}

P_i = np.zeros(N)
ans = {}
for i in sorted_Y:
    city = Y.index(i)+1
    ans[city] = i

for i in ans:
    p,y = cities[i]
    print('{0:06}{1:06}'.format(p, i))


Fixed submission:
import numpy as np
N, M = map(int, input().split())
cities = {}
P = {}
Y = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = p
    Y[i] = y

ans = {}
sorted_Y = sorted(Y.items(), key=lambda x:x[1])
P_i = np.zeros(N)
for i,y in sorted_Y:
    p = cities[i]
    P_i[p-1] += 1
    ans[i] = (p, int(P_i[p-1]))

for i in range(M):
    print('{0:06}{1:06}'.format(ans[i][0], ans[i][1]))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
cities = {}
P = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = (p,y)
    if not p in P:
        P[p] = [y]
    else:
        P[p].append(y)

sorted_P = {p:sorted(P[p]) for p in P}

for i in range(M):
    city_p, city_y = cities[i]
    x = sorted_P[city_p].index(city_y)+1
    print('{0:06}{1:06}'.format(city_p, x))


Fixed submission:
import numpy as np
N, M = map(int, input().split())
cities = {}
P = {}
Y = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = p
    Y[i] = y

ans = {}
sorted_Y = sorted(Y.items(), key=lambda x:x[1])
P_i = np.zeros(N)
for i,y in sorted_Y:
    p = cities[i]
    P_i[p-1] += 1
    ans[i] = (p, int(P_i[p-1]))

for i in range(M):
    print('{0:06}{1:06}'.format(ans[i][0], ans[i][1]))