Problem:
 Score: 300 points    Problem Statement In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to those prefectures.  City i is established in year Y_i and belongs to Prefecture P_i .  You can assume that there are no multiple cities that are established in the same year.  It is decided to allocate a 12 -digit ID number to each city.  If City i is the x -th established city among the cities that belong to Prefecture i , the first six digits of the ID number of City i is P_i , and the last six digits of the ID number is x .  Here, if P_i or x (or both) has less than six digits, zeros are added to the left until it has six digits.  Find the ID numbers for all the cities.  Note that there can be a prefecture with no cities.      Constraints  1 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq P_i \leq N  1 \leq Y_i \leq 10^9  Y_i are all different.  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  P_1  Y_1  :  P_M  Y_M       Output Print the ID numbers for all the cities, in ascending order of indices (City 1 , City 2 , ... ).        Sample Input 1 2 3
1 32
2 63
1 12      Sample Output 1 000001000002
000002000001
000001000001   As City 1 is the second established city among the cities that belong to Prefecture 1 , its ID number is 000001000002 .  As City 2 is the first established city among the cities that belong to Prefecture 2 , its ID number is 000002000001 .  As City 3 is the first established city among the cities that belong to Prefecture 1 , its ID number is 000001000001 .        Sample Input 2 2 3
2 55
2 77
2 99      Sample Output 2 000002000001
000002000002
000002000003

Solution (Python):
import bisect

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

P = []
Y = []
PY = []
dic = {}
for i in range(M):
    p,y = map(int,input().split())
    P.append(p)
    Y.append(y)

    dic[y] = ''

    PY.append((p,y))

PY = sorted(PY)
P  = sorted(P)
lenP = len(P)
left = 0
righ = 0
for i in range(1,N+1):

    t_list = []

    left = bisect.bisect_left(P,i,0,lenP)
    righ = bisect.bisect_right(P,i,0,lenP)

    
    

    if i == P[left]:
        for j in range(left,righ):
            t_list.append(PY[j][1])
        t_list = sorted(t_list)
        for k in range(len(t_list)):
            y = t_list[k]
            dic[y] = str(i).zfill(6) + str(k+1).zfill(6)

    if lenP == righ:
        
        break

for y in Y:
    print(dic[y])

Solution (Python):
N, M = map(int, input().split())
timeline = []
for i in range(M):
    P, Y = map(int, input().split())
    timeline.append((Y, P, i))
timeline.sort()
count = [0] * (N + 1)
number = [(0, 0)] * M
for y, p, i in timeline:
    count[p] += 1
    number[i] = (p, count[p])
for i in range(M):
    print('{:06}{:06}'.format(number[i][0], number[i][1]))

Solution (Python):
from operator import itemgetter

def main():
    N,M = list(map(int, input().split()))
    lst = [[] for i in range(N)]
    anslst = []

    for i in range(M):
        P,Y = list(map(int, input().split()))
        lst[P-1].append({'city_id':i, 'pref':P, 'year':Y})

    for i in range(N):
        tmp = lst[i]
        tmp = sorted(tmp, key = itemgetter('year'))
        for j in range(len(tmp)):
            city_id = tmp[j]['city_id']
            pref = tmp[j]['pref']
            year = tmp[j]['year']
            id = '{0:06d}'.format(pref) + '{0:06d}'.format(j+1)
            anslst.append({'city_id':city_id, 'pref':pref, 'year':year, 'id':id})

    anslst = sorted(anslst, key = itemgetter('city_id'))
    for i in range(len(anslst)):
        print(anslst[i]['id'])

if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import collections
n, m = map(int, input().split())
a = [ [ int(s) for s in input().split() ] for _ in range(m) ]
f = collections.defaultdict(list)
for x, y in sorted(a):
    f[x] += [ y ]
for x, y in a:
    z = bisect.bisect(f[x], y)
    print("%06d%06d" % (x, z))

Solution (Python):
from operator import itemgetter


def main():
    n, m = [int(e) for e in input().split()]
    l = []
    for i in range(m):
        p, y = [int(e) for e in input().split()]
        l.append((i, p, y))

    sorted_l = sorted(l, key=itemgetter(1, 2))
    
    

    n_nums = []
    pref = None
    for e in sorted_l:
        p = e[1]
        if (pref is None) or p != pref:
            pref = p
            c = 1
        p_str = str(p).zfill(6)
        c_str = str(c).zfill(6)
        nums = p_str + c_str
        n_nums.append((e[0], nums))
        c += 1

    for num in sorted(n_nums, key=itemgetter(0)):
        print(num[1])


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import collections
n, m = map(int, input().split())
a = [ [ int(s) for s in input().split() ] for _ in range(m) ]
f = collections.defaultdict(list)
for x, y in sorted(a):
    f[x] += [ y ]
for x, y in a:
    z = bisect.bisect(f[x], y)
    print("%06d%06d" % (x, z))

Solution (Python):
n,m=map(int,input().split())
pref=[[] for i in range(n)]
id_number=[0 for i in range(m)]
for i in range(m):
	p,y=map(int,input().split())
	pref[p-1].append([y,i])

for i in range(n):
	pref_data=sorted(pref[i])
	for j in range(len(pref_data)):
		id_number[pref_data[j][1]]=str(1000000000000+1000000*(i+1)+j+1)

for i in range(len(id_number)):
	print(id_number[i][1:])

Solution (Python):
N,M = map(int,input().split())
shi_lst = [list(map(int,input().split())) for i in range(M)]
shi_sorted = sorted(shi_lst)


ans = {}
tmp = shi_sorted[0][0] 
count = 0
for i in range(M):
  count += 1
  if tmp != shi_sorted[i][0]:
    count = 1
    tmp = shi_sorted[i][0]
  ans[str(shi_sorted[i][1])] = ("%06d"%tmp) + ("%06d"%count) 




for i in range(M):
  print(ans[str(shi_lst[i][1])])

Solution (Python):
N,M=map(int,input().split())
data=[]
for m in range(M):
    data.append(list(map(int,input().split())))
    data[m].append(m)

data.sort(key=lambda x:x[1])
data.sort(key=lambda x:x[0])

pref=0
count=0
for m in range(M):
    count+=1
    if data[m][0]!=pref:
        count=1
    pref=data[m][0]
    ID=('000000'+str(data[m][0]))[-6:]+('000000'+str(count))[-6:]
    data[m].append(ID)

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

for m in range(M):
    print(data[m][3])

Solution (Python):

import bisect
import collections
n, m = map(int, input().split())
a = [ [ int(s) for s in input().split() ] for _ in range(m) ]
f = collections.defaultdict(list)
for x, y in sorted(a):
    f[x] += [ y ]
for x, y in a:
    z = bisect.bisect(f[x], y)
    print("%06d%06d" % (x, z))

Solution (Python):
n,m=map(int,input().split())
pref=[[] for i in range(n)]
id_number=[0 for i in range(m)]
for i in range(m):
	p,y=map(int,input().split())
	pref[p-1].append([y,i])

for i in range(n):
	pref_data=sorted(pref[i])
	for j in range(len(pref_data)):
		id_number[pref_data[j][1]]=str(1000000000000+1000000*(i+1)+j+1)

for i in range(len(id_number)):
	print(id_number[i][1:])

Solution (Python):
N, M = map(int, raw_input().split())

number_dict = {}

for i, m in enumerate(range(M)):
    P, Y = map(int, raw_input().split())

    if P in number_dict:
        number_dict[P].append([i+1, Y])
    else:
        number_dict[P] = [[i+1, Y]]

L = list(number_dict.items())

result = []

for l in L:
    prefix = '%06d' % l[0]
    l[1].sort(key=lambda x: x[1])
    for i, city in enumerate(l[1]):
        number = '%06d' % (i+1)
        order = city[0]
        result.append([order, prefix+number])

result.sort(key=lambda x: x[0])
for r in result:
    print r[1]

Solution (Python):
from operator import itemgetter

n,m=map(int,input().split())
s = [ list(map(int,input().split())) for _ in range(m)]
l = sorted(s,key=itemgetter(0,1))
j=1
res = {}
for i in range(0,len(l)):
    if i !=0 and l[i][0] != l[i-1][0]:
        j = 1
    res[l[i][1]] = ('%06d' % l[i][0]) + ('%06d' % j)
    j = j + 1
for i in range(0,len(s)):
    print(res[s[i][1]])

Solution (Python):
import sys

N, M = map(int, input().split())
PYI = [list(map(int, line.split())) for line in sys.stdin.readlines()]

for i in range(M):
    PYI[i].append(i)

PYI.sort(key = lambda x: x[1])

num = [0] * (N + 1)

ans = [None] * M

for p, y, i in PYI:
    ans[i] = str(p).zfill(6) + str(num[p] + 1).zfill(6)
    num[p] += 1

for s in ans:
    print(s)

Solution (Python):
N,M = map(int,input().split())
PY = []
tmp = []
cheker = []
res = []
for i in range(M):
    tmp = list(map(int,input().split()))
    tmp.append(i)
    PY.append(list(tmp))
    res.append('')

sorted_py = sorted(PY, key=lambda x: x[1])
checker = [0 for i in range(N)]

for i in range(M):
    index = sorted_py[i][0]-1
    checker[index] += 1
    res[sorted_py[i][2]] = str(sorted_py[i][0]).zfill(6) + str(checker[sorted_py[i][0]-1]).zfill(6)

for i in range(M):
    print(res[i])

Solution (Python):
import copy
nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
all_city = list()
for i in range(m):
    py = list(map(int, input().split()))
    py.append(i)
    all_city.append(py)
ac_list = copy.deepcopy(all_city)
ac_list.sort()
ac_dict = {}
a = 0
b = 0
for i in range(m):
    if ac_list[i][0] == a:
        b += 1
    else:
        a = ac_list[i][0]
        b = 1
    ac_dict[ac_list[i][2]] = str(str(a).zfill(6) + str(b).zfill(6))
for i in range(m):
    print(ac_dict.get(all_city[i][2]))

Solution (Python):
import heapq
N, M = map(int, input().split())
P = [0 for i in range(M)]
Y = [0 for i in range(M)]
country = [[] for i in range(N+1)]
for i in range(M):
    P[i], Y[i] = map(int, input().split())
    heapq.heappush(country[P[i]], (Y[i],i))
cs = [0 for i in range(M)]
for i in range(N+1):
    ran = len(country[i])
    for j in range(ran):
        year, num = heapq.heappop(country[i])
        cs[num] = str(j+1).zfill(6)

for i in range(M):
    line = str(P[i]).zfill(6) + cs[i]
    print(line)

Solution (Python):
from math import log10
n, m = map(int, input().split())
P = [[] for i in range(n)]
for i in range(m):
    p, y = map(int, input().split())
    P[p-1].append((y, i+1))
for i in range(n):
    P[i].sort(key=lambda x:x[0])
res = []
for i in range(n):
    for j in range(len(P[i])):
        a = int(log10(i+1)) + 1
        b = int(log10(j+1)) + 1
        c = (6-a) * "0"
        c += str(i+1)
        c += (6-b) * "0"
        c += str(j+1)
        res.append((c, P[i][j][1]))
res.sort(key=lambda x:x[1])
for i in range(len(res)):
    print(res[i][0])

Solution (Python):
N, M = map(int, input().split())		

P=[0]
Y=[0]
A=[]

for i in range(M):
	p, y = map(int, input().split())		
	P.append(p)
	Y.append(y)
	A.append([i,p,y,p*100000000000 + y])






A = sorted(A, key=lambda x: x[3])



p0=0
no=0
for i in range(len(A)):
	a=A[i]
	p=a[1]
	y=a[2]

	
	if(p!=p0):no=0
	no+=1
	A[i].append(no)
	
	p0=p



A = sorted(A, key=lambda x: x[0])


for a in A:
	p = "000000" + str(a[1])
	i = "000000" + str(a[4])
	print(p[-6:]+i[-6:])

Solution (Python):
N, M = (int(i) for i in input().split(' '))
py=[]
p =[]


for i in range(M):
    p = [i]
    p.extend([int(j) for j in input().split(' ')])
    py.append(p)


py.sort(key = lambda x: x[2])
pcid = [1] * N 

for i in range(M):
    p = py[i][1] 
    py[i][2] = pcid[p-1]
    pcid[p-1] += 1

py.sort(key=lambda x:x[0])
for t in py:
    print('{0:0>6}{1:0>6}'.format(t[1],t[2]))

Solution (Python):
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
import bisect


MOD = 10 ** 9 + 7

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

KenList = [[] for _ in range(N)]

PYlist = [None] * M
for i in range(M):
    P, Y = [int(x) for x in input().split()]
    P = P - 1
    PYlist[i] = (P, Y)
    KenList[P].append((i, Y))


for i in range(N):
    KenList[i] = sorted(KenList[i], key=lambda x: x[1])

cityOrder = [None] * N
for i in range(N):
    kl = KenList[i]
    dic = {}
    for j in range(len(kl)):
        city = kl[j][0]
        dic[city] = j
    cityOrder[i] = dic


for i in range(M):
    ken = PYlist[i][0]
    kl = KenList[ken]
    idx = cityOrder[ken][i]
    
    
    
    

    print("{0:06d}{1:06d}".format(ken+1, idx+1))


sys.exit(0)

Solution (Python):
N,M = map(int,input().split())
P = []
Y = []
arr = [[]for j in range(10**5+1)]
for i in range(M):
  listA = list(map(int,input().split()))
  P.append(listA[0])
  Y.append(listA[1])
  arr[listA[0]].append(listA[1])
for i in range(N+1):
  arr[i].sort()
for i in range(M):
  
  left = 0
  right = len(arr[P[i]])-1
  while left <= right:
    mid = (left+right)//2
    if arr[P[i]][mid] == Y[i]:
      k = mid
      break
    elif arr[P[i]][mid] > Y[i]:
      right = mid-1
    else:
      left = mid+1
  print(str(P[i]).rjust(6,'0')+str(k+1).rjust(6,'0'))

Solution (Python):
N, M = map(int, input().split(" "))
ary = [list(map(int, input().split(" ") + [i])) for i in range(M)]

sort_ary = sorted(ary, key=lambda x: (x[0], x[1]))

ken = sort_ary[0][0]
index = 1
for node in sort_ary:
    if ken != node[0]:
        ken = node[0]
        index = 1
    node += [index]
    index += 1

ans_ary = sorted(sort_ary, key=lambda x: x[2])

r = ""
for node in ans_ary:
    r += "%06d"%node[0] + "%06d"%node[3] + "\n"

print(r[:-1])

Solution (Python):
N,M=list(map(int,input().split()))
d=[]
for i in range(M):
    p,y=list(map(int,input().split()))
    d.append([p,y,i])

ans=[]
d.sort()
num=1
year=1
i=0
while(i<len(d)):
    if(d[i][0]==num):
        ans.append(['{0:06d}'.format(num)+'{0:06d}'.format(year),d[i][2]])
        year+=1
        i+=1
    else:
        year=1
        num+=1
ans.sort(key=lambda x:x[1])
for i in ans:
    print(i[0])

Solution (Python):
n, m = map(int, input().split())

city_list = []
for i in range(m):
	p, y = map(int, input().split())
	city_list.append([i, p, y, 0])

city_list = sorted(city_list, key = lambda x: x[2])
city_list = sorted(city_list, key = lambda x: x[1])

nowp = 1
index = 1
for city in city_list:
	if city[1] == nowp:
		city[3] = index
		index += 1
	else:
		nowp = city[1]
		index = 1
		city[3] = index
		index += 1

city_list = sorted(city_list, key = lambda x: x[0])

for city in city_list:
	kami_str = '0' * (6 - len(str(city[1]))) + str(city[1])
	shimo_str = '0' * (6 - len(str(city[3]))) + str(city[3])
	answer = kami_str + shimo_str
	print(answer)

Solution (Python):
n, m = map(int, input().split())
city = []
city_dict = {}
for i in range(m):
    tmp1, tmp2 = map(int, input().split())
    city.append([tmp1, tmp2])
    if tmp1 not in city_dict.keys():
        city_dict[tmp1] = [tmp2]
    else:
        city_dict[tmp1].append(tmp2)




for i in city_dict.keys():
    city_dict[i].sort()
    city_list = zip(city_dict[i], range(len(city_dict[i])))
    city_dict[i] = dict(city_list)





for i in range(m):
    tmp1 = city[i][0]
    tmp2 = city[i][1]
    
    
    print("{:06}{:06}".format(tmp1, city_dict[tmp1][tmp2]+1))

Solution (Python):
n,m=map(int,input().split())
A=[[int(i) for i in input().split()] for j in range(m)]
B={}
for i in range(m):
    A[i].append(i)
A=sorted(A,key=lambda year:year[1])
for i in A:
    if i[0] not in B:
        B[i[0]]=1
        i+=[B[i[0]]]
    else:
        B[i[0]]+=1
        i+=[B[i[0]]]
A=sorted(A,key=lambda index:index[2])
for i in A:
    print(str(i[0]).zfill(6)+str(i[3]).zfill(6))

Solution (Python):
N, M = map(int, input().split())
P = [0]*M
Y = [0]*M
T = [0]*M
d = {}
for i in range(M):
    P[i], Y[i] = map(int, input().split())
    if not P[i] in d.keys():
        d[P[i]] = []
    d[P[i]].append([Y[i],i])
for k in d:
    d[k].sort(key=lambda x:x[0])
    for i in range(len(d[k])):
        T[d[k][i][1]] = i+1
for i in range(M):
    print('%06d' % P[i] + '%06d' % T[i])

Solution (Python):
ls = input().strip().split(' ')
N = int(ls[0])
M = int(ls[1])
ls = []
for i in range(M):
    ln = input().strip().split(' ')
    ls.append((ln[0], int(ln[1]), i))
ls.sort()
result = []
x = 1
lst = -1
for i in ls:
    if i[0] == lst:    x += 1
    else:    x = 1
    result.append((i[2], '{:06d}{:06d}'.format(int(i[0]), x)))
    lst = i[0]
result.sort()
for i in result:
    print(i[1])

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]

PY_list = defaultdict(list)
for i in range(len(PY)):
    PY_list[PY[i][0]].append([i, PY[i][1]])


py_opt = dict()
for pyl in PY_list.values():
    pyl.sort(key = lambda x: x[1])
    for i in range(len(pyl)):
        
        py_opt[pyl[i][0]] = i



for i in range(len(PY)):
    
    n = py_opt[i]
    print("{:06d}{:06d}".format(PY[i][0], n + 1))

Solution (Python):
n,m = input().split()
plist = []
ylist = []
n = int(n)
m = int(m)
anslist = [0 for i in range(m)]
list = [[] for i in range(n+1)]
for i in range(m):
    p,y = input().split()
    p = int(p)
    y = int(y)
    plist.append(p)
    ylist.append(y)
    list[p-1].append([ylist[i],i])
for i in range(n):
    list[i].sort()
    for j in range(len(list[i])):
        mtem = list[i][j][1]
        ans1 = str(plist[mtem])
        while len(ans1) < 6:
            ans1 = "0" + ans1
        ans2 = str(j+1)
        while len(ans2) < 6:
            ans2 = "0" + ans2
        anslist[mtem] = ans1 + ans2
for i in range(m):
    print(anslist[i])

Solution (Python):
import operator
N, M = map(int, raw_input().split(" "))

PY = []
for i in range(M):
    py = map(int, raw_input().split(" "))
    py.append(i)
    PY.append(py)

PY.sort(key=operator.itemgetter(0, 1))

j = PY[0][0]
count = -1
for i in range(M):
    count += 1
    if j!= PY[i][0]:
        count = 0
        j = PY[i][0]
    PY[i].append(count)

PY.sort(key=operator.itemgetter(2))

for i in PY:
    print ("000000" + str(i[0]))[-6:]+ ("000000"+ str(i[3]+1))[-6:]

Solution (Python):
from operator import itemgetter
A=[]
n,m=[int(i) for i in input().split()]
B=[1]*(n+1)
for i in range(m):
    a=[int(j) for j in input().split()]
    a.append(i)
    A.append(a)
A.sort(key=itemgetter(1))
for i in range(m):
    A[i].append(B[A[i][0]])
    B[A[i][0]]+=1
A.sort(key=itemgetter(2))
for i in range(m):
    c=6-len(str(A[i][0]))
    d=6-len(str(A[i][3]))
    print("{}{}{}{}".format("0"*c,A[i][0],"0"*d,A[i][3]))

Solution (Python):
import numpy as np
N, M = map(int, input().split())
towns = []
for i in range(M):
  towns.append(list(map(int, input().split()))+[i])

towns= sorted(towns, key=lambda x:x[1])
dic = {}
for i in range(M):
  if towns[i][0] in dic:
    towns[i].append(dic[towns[i][0]])
    dic[towns[i][0]] += 1
  else:
    dic[towns[i][0]] = 1
    towns[i].append(dic[towns[i][0]])
    dic[towns[i][0]] += 1
    
    
towns = sorted(towns, key=lambda x:x[2])

for i in range(M):
  s1 = "{0:06d}".format(towns[i][0])
  s2 = "{0:06d}".format(towns[i][3])
  print(s1+s2)

Solution (Python):
import numpy as np

N, M = map(int, input().split())
P = []
Y = []
for _ in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)
P = np.array(P)
Y = np.array(Y)
PY = np.c_[P, Y]
sort_ind = np.argsort(Y)

PY_sort = PY[sort_ind]
count = [0] * (int(1e+5) + 1)
id_list = []
for p, y in PY_sort:
    count[p] += 1
    id_list.append(str(p).zfill(6) + str(count[p]).zfill(6))

id_list = np.array(id_list)
id_list = id_list[np.argsort(sort_ind)]
for city_id in id_list:
    print(city_id)

Solution (Python):
"""
C - ID
"""
import numpy as np

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


p_y = []
list_n = 0
for n in range(m):
    p, y = map(int, input().split())
    p_y.append([list_n, p, y, 0])
    list_n += 1

p_y_np = np.array(p_y, dtype=np.int)



pref_set = list(set(list(p_y_np[:, 1])))


pref_count = {}
for part in pref_set:
    pref_count[part] = 1



year_sort = np.argsort(p_y_np[:, 2])

for p_y_row in p_y_np[year_sort]:
    
    pref = p_y_row[1]
    index = p_y_row[0]

    p_y_np[index, 3] = pref_count[pref]
    pref_count[pref] += 1



for part in p_y_np:
    print("%06d%06d" % (part[1], part[3]))

Solution (Python):
import numpy as np

N, M = map(int, input().split())
P = []
Y = []
for _ in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)
P = np.array(P)
Y = np.array(Y)
PY = np.c_[P, Y]
sort_ind = np.argsort(Y)

PY_sort = PY[sort_ind]
count = [0] * (int(1e+5) + 1)
id_list = []
for p, y in PY_sort:
    count[p] += 1
    id_list.append(str(p).zfill(6) + str(count[p]).zfill(6))

id_list = np.array(id_list)
id_list = id_list[np.argsort(sort_ind)]
for city_id in id_list:
    print(city_id)

Solution (Python):
from operator import itemgetter

def main():
    num_prefecture, num_city = list(map(int, input().rstrip().split()))
    prefecture_list = []
    for i in range(num_prefecture):
        prefecture_list.append([])
    
    id_list = []
    for idx_city in range(num_city):
        p_belong, y_born = list(map(int, input().rstrip().split()))
        p_belong -= 1 
        prefecture_list[p_belong].append([idx_city, y_born])
    
    
    
    for l in prefecture_list:
        l.sort(key = itemgetter(1))
    
    
    
    for idx_p, l in enumerate(prefecture_list):
        for x, [idx_city, y_born] in enumerate(l):
            id_first = '{0:06d}'.format(idx_p + 1)
            id_end = '{0:06d}'.format(x + 1)
            id_num = str(id_first) + str(id_end)
            id_list.append([idx_city, id_num])
    
    id_list.sort(key = itemgetter(0))
    
    for id_num in id_list:
        print(id_num[1])
    
if __name__ == '__main__':
    main()

Solution (Python):
[N,M] = [int(x) for x in input().split()]

m = [[] for i in range(N)]

def toid(p,n):
    return "%06d%06d" % (p,n)

ids=["" for i in range(M)]
for i in range(M):
    [p,y] = [int(x) for x in input().split()]
    m[p-1].append((i,y))
    

for p in range(N):
    if len(m[p]) == 0:
        continue
    nn = sorted(m[p],key=lambda x:x[1])

    for n,(i,y) in enumerate(nn): 
        ids[i] = toid(p+1,n+1)

print("\n".join(ids))

Solution (Python):
n,m=map(int,input().split())
cities=[list(map(int,input().split()))+[i] for i in range(m)]
i=0
pre_pref=0

res=['' for _ in range(m)]
for idx,city in enumerate(sorted(cities)):
    if pre_pref!=city[0]:
        i=0
        pre_pref=city[0]
    i+=1
    res[city[2]]='{:06}{:06}'.format(city[0],i)
print('\n'.join(res))

Solution (Python):
"""
C - ID
"""
import numpy as np

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


p_y = []
list_n = 0
for n in range(m):
    p, y = map(int, input().split())
    p_y.append([list_n, p, y, 0])
    list_n += 1

p_y_np = np.array(p_y, dtype=np.int)



pref_set = list(set(list(p_y_np[:, 1])))


pref_count = {}
for part in pref_set:
    pref_count[part] = 1



year_sort = np.argsort(p_y_np[:, 2])

for p_y_row in p_y_np[year_sort]:
    
    pref = p_y_row[1]
    index = p_y_row[0]

    p_y_np[index, 3] = pref_count[pref]
    pref_count[pref] += 1



for part in p_y_np:
    print("%06d%06d" % (part[1], part[3]))

Solution (Python):
import numpy as np
N , M = map(int, input().split())
P = [0]*M
Y = [0]*M
for i in range(M):
    P[i],Y[i] =  map(int, input().split())

Y_ = np.argsort(Y)
count = [1]*(N+1)
ans = [0]*M
for i in range(M):
    ans[Y_[i]] = str(P[Y_[i]]).zfill(6) + str(count[P[Y_[i]]]).zfill(6)
    count[P[Y_[i]]] = count[P[Y_[i]]] +1
 
for i in range (M):
    print(ans[i])

Solution (Python):

"""
Created on Sun Nov  4 18:54:20 2018
ABC113C
@author: maezawa
"""

n, m = list(map(int, input().split()))
p = [0]
y = [0]
for i in range(m):
    pi, yi = list(map(int, input().split()))
    p.append(pi)
    y.append(yi)



    
cityn = ['']*m

ps = [[] for _ in range(n+1)]
for i in range(1,m+1):
    ps[p[i]].append(i)
    
for j in range(1,n+1):
    ps[j].sort(key = lambda x: y[x])
    for i, k in enumerate(ps[j]):
        left = '000000'+ str(j)
        right = '000000' + str(i+1)
        cityn[k-1] = left[len(left)-6:] + right[len(right)-6:]

for i in range(m):
    print(cityn[i])

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

d = {}
for i in range(m):
    p, y = list(map(int, input().split()))

    if p not in d:
        d[p] = [[y, i]]
    else:
        d[p].append([y, i])

for i in d:
    d[i].sort()

ans = {}
for i in d:
    for j in range(len(d[i])):
        ans[d[i][j][1]] = '{0:06d}'.format(i) + '{0:06d}'.format(j + 1)

for i in range(m):
    print(ans[i])

Solution (Python):
n, m = map(int, input().split())
P = [0]*(m+1)
Y = [0]*(m+1)
for i in range(1, m+1):
    P[i], Y[i] = map(int, input().split())
PP = [[] for i in range(n+1)]

for i in range(1, m+1):
    p = P[i]
    y = Y[i]
    PP[p].append((i, y))

C = []
for i in range(1, n+1):
    if len(PP[i]) == 0:
        continue
    if len(PP[i]) > 1:
        PP[i].sort(key=lambda x: x[1])
    for j, pp in enumerate(PP[i]):
        num = '%06d%06d' % (P[pp[0]], j+1)
        C.append((pp[0], num))

C.sort(key=lambda x: x[0])
for i, num in C:
    print(num)

Solution (Python):
n, m = map(int, input().split())
data = [0] * m
res = [0] * m
for i in range(m):
    d = list(map(int, input().split()))
    d.append(i)
    data[i] = tuple(d)
data.sort()
city_num = data[0][0]
birth_num = 1

for item in data:
    
    if item[0] != city_num:
        city_num = item[0]
        birth_num = 1
    res[item[2]] = '{:06d}{:06d}'.format(item[0], birth_num)
    birth_num += 1
for item in res:
    print(item)

Solution (Python):
[n,m]=[int(i) for i in input().split()]
py=[]
for i in range(m):
    temp=[int(i) for i in input().split()]
    py.append([i+1, temp[0], temp[1]])

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

count=[0 for i in range(n)]

ans=[]


for i in py:
    
    count[i[1]-1]+=1
    ans.append([i[0], i[1], count[i[1]-1]])

ans.sort(key=lambda x:x[0])
for i in ans:
    a1=str(i[1])
    
    c1=len(a1)
    while c1<6:
        print("0", end="")
        c1+=1
    print(a1, end="")

    a2=str(i[2])
    c2=len(a2)
    while c2<6:
        print("0", end="")
        c2+=1
    print(a2)

Solution (Python):
[n,m]=[int(i) for i in input().split()]
py=[]
for i in range(m):
    temp=[int(i) for i in input().split()]
    py.append([i+1, temp[0], temp[1]])

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

count=[0 for i in range(n)]

ans=[]


for i in py:
    
    count[i[1]-1]+=1
    ans.append([i[0], i[1], count[i[1]-1]])

ans.sort(key=lambda x:x[0])
for i in ans:
    a1=str(i[1])
    
    c1=len(a1)
    while c1<6:
        print("0", end="")
        c1+=1
    print(a1, end="")

    a2=str(i[2])
    c2=len(a2)
    while c2<6:
        print("0", end="")
        c2+=1
    print(a2)

Solution (Python):
import time
import numpy as np


"""
n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
"""

n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
p = [[] for _ in range(n)]
start = time.time()
for _p, _y in py:
    p[_p - 1].append(_y)

for i in range(n):
    p[i] = np.argsort(np.argsort(p[i]))


counter = [0 for _ in range(n)]
for _p, _y in py:
    
    
    
    t = "{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1)
    print(t)
    counter[_p - 1] += 1

Solution (Python):
import time
import numpy as np


"""
n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
"""

n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
p = [[] for _ in range(n)]
start = time.time()
for _p, _y in py:
    p[_p - 1].append(_y)

for i in range(n):
    p[i] = np.argsort(np.argsort(p[i]))


counter = [0 for _ in range(n)]
for _p, _y in py:
    
    
    
    t = "{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1)
    print(t)
    counter[_p - 1] += 1

Solution (Python):
import copy as cp

def bin_search(n,lst):
    l=0
    r=len(lst)
    
    while r-1>=l:
        i=(l+r)//2
        if lst[i]==n: return i
        elif lst[i]<n: l=i+1
        else: r=i

N,M = map(int,input().split())
P = []
Y = []
for i in range(M):
    p,y = map(int,input().split())
    P.append(p)
    Y.append(y)


C_lst = [[] for _ in range(N)]
for i in range(M):
    C_lst[P[i]-1].append(Y[i])

C_cp = cp.deepcopy(C_lst)
for i in range(N):
    C_cp[i].sort()
for i in range(M):
    ans = "0"*(6-len(str(P[i]))) + str(P[i])
    idx = bin_search(Y[i],C_cp[P[i]-1]) + 1
    ans += "0"*(6-len(str(idx))) + str(idx)
    print(ans)

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
prefs = [list(map(int, input().split())) for _ in range(M)]
dict = defaultdict(list) 
result_dict = defaultdict(list) 
count = 1

for pref in prefs:
    dict[pref[0]].append([pref[1], count])
    count += 1

for k, v in dict.items():
    dict[k] = sorted(v)

for k, v in dict.items():
    for i in range(len(v)):
        result_dict[v[i][1]] = '{0:06d}'.format(k) + '{0:06d}'.format(i+1)

for v in result_dict.values():
    print(v)

Solution (Python):


class City:
    def __init__(self, id, pref, year):
        self.id = id
        self.pref = pref
        self.year = year
        self.num = 0

N,M = map(int, input().split())
cities = []
for i in range(M):
    p, y = map(int, input().split())
    cities.append(City(i+1, p, y))

cities.sort(key=lambda city: city.year)

p_cnt = [0] * N
for i in range(M):
    
    pref_num = str(cities[i].pref).zfill(6)
    p_cnt[cities[i].pref-1] += 1
    city_num = str(p_cnt[cities[i].pref-1]).zfill(6)
    cities[i].num = pref_num + city_num

cities.sort(key=lambda city: city.id)

for i in range(M):
    print(cities[i].num)

Solution (Python):
N, M = map(int, raw_input().split())
IPY = [[i]+map(int, raw_input().split()) for i in range(M)]
IPY_y_sorted = sorted(IPY, key=lambda x:x[2])
ans = [long(0)]*M
P_count = [0]*N
for ipy in IPY_y_sorted:
  P_count[ipy[1]-1] += 1
  ans[ipy[0]] = long(ipy[1]*1e6)+P_count[ipy[1]-1]
for a in ans:
  print "%012d"%a

Solution (Python):



def ID():
    N, M = [int(n) for n in input().split()]
    lst = [[n for n in input().split()] for _ in range(M)]
    sorted_lst = sorted(lst, key=lambda x: int(x[1]))
    memo = {}
    result = {}
    for p, x in sorted_lst:
        if p not in memo:
            memo[p] = 1
        else:
            memo[p] += 1
        higher = p.zfill(6)
        lower = "{0:06d}".format(memo[p])
        result[p + x] = higher + lower

    for p, x in lst:
        print(result[p+x])


if __name__ == '__main__':
    ID()

Solution (Python):
n, m = map(int, input().split())
ps = []
for i in range(m):
    p, y = map(int, input().split())
    ps.append([p, y, i+1])

ps = sorted(ps)
ps

ans = []
count = 1
for i in range(m):
    if (i != 0 and (ps[i])[0] != (ps[i-1])[0]):
        count = 1
    else:
        pass
    ans.append([(ps[i])[2], 1000000*((ps[i])[0]) + count])
    count += 1

ans = sorted(ans)

for i in ans:
    aw = i[1]
    aww = str(aw).zfill(12)
    print(aww)

Solution (Python):
n,m=map(int,input().split())
lp=[[] for i in range(n)]
ln={}
for i in range(m):
  p,y=map(int,input().split())
  lp[p-1].append(y)
  ln[i]=str(p)+','+str(y)

lcode={}
for i in range(n):
  p = i+1
  lp[i]=sorted(lp[i])
  for j in range(len(lp[i])):
    lcode[str(p)+','+str(lp[i][j])]=format(p,'06d')+format(j+1,'06d')

for i in range(m):
  print(lcode[ln[i]])

Solution (Python):
n, m = [int(x) for x in input().split()]
l = []
for i in range(m):
    tmp = [int(x) for x in input().split()]
    l.append([i, tmp[0], tmp[1]])
l.sort(key=lambda x: x[2])

prefecture = [0 for _ in range(n)]
city = [[] for _ in range(m)]

for info in l:
    i, p, y = info
    tmp = [p, prefecture[p-1]+1]
    prefecture[p-1] += 1
    city[i] = tmp

for x in city:
    p_str = str(x[0])
    c_str = str(x[1])
    p_add = '0'*(6 - len(p_str))
    c_add = '0' * (6 - len(c_str))
    p_str = p_add + p_str
    c_str = c_add + c_str
    print(p_str + c_str)

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

py = []

for i in range(m):
    py.append(list(map(int, input().split())))

mapa ={}

for i in range(m):
    if py[i][0] in mapa:
        mapa[py[i][0]][py[i][1]] = i
    else:
        mapa[py[i][0]] = {py[i][1]:i}

ans = ['' for _ in range(m)]

for i in mapa:
    pri = mapa[i]
    pri = sorted(pri.items())
    for j in range(len(pri)):
        ans[pri[j][1]] = ('000000' + str(i))[-6:] + ('000000' + str(j + 1))[-6:]
for i in ans:
    print(i)