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):
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]

for i in range(m):
	a[i].append(i)
b = sorted(a)

count = 1

for i in range(m):
	temp = b[i][2]
	b[i].pop(2)
	b[i].insert(0, temp)
	b[i].append(count)
	count += 1
	if i == m - 1:
		continue
	if b[i][1] != b[i + 1][0]:
		count = 1
b.sort()
for i in range(m):
	print(str(b[i][1]).zfill(6) + str(b[i][-1]).zfill(6))

Solution (Python):
N,M=map(int,input().split())
L=[[] for i in range(N+1)]
A=[]
for i in range(M):
  P,Y=map(int,input().split())
  L[P].append([i,Y])
for i in range(1,N+1):
  li=sorted(L[i],key=lambda x:x[1])
  k=0
  for city in li:
    k+=1
    A.append([city[0],str(i).zfill(6)+str(k).zfill(6)])
A.sort(key=lambda x:x[0])
for item in A:
  print(item[1])

Solution (Python):
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, M = rdi()

PY = []
for i in range(M):
        p, y = rdi()
        PY.append( (p, y, i) )

spy = sorted(PY)

codes = []
lastp = -1
pj = 0
for k in range(M):
        p, y, i = spy[k]
        if p != lastp:
                lastp = p
                cj = 1
        else:
                cj = cj + 1
        code = "%06d%06d" % (int(p), cj)
        codes.append( (i, code) )

codes = sorted(codes)

for i in range(M):
        print codes[i][1]

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

l = []
ans = [0] * m

for i in range(m):
    l.append([int(j) for j in input().split()])
    l[i].append(i)


l2 = sorted(l, key=lambda x:(x[0],x[1]))
cnt = 1

for i in range(m):
    
    l2[i][1] = cnt
    
    if i < m -1 and l2[i][0] == l2[i + 1][0]:
        cnt += 1
    else:
        cnt = 1

    ans[l2[i][2]] = '{:06}{:06}'.format(l2[i][0],l2[i][1])

for s in ans:
    print(s)

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

citys.sort(key = lambda x:x[1])
nums = [0]*(N+1)
states = [None]*M

for p,y,i in citys:
    nums[p] += 1
    states[i] = [str(p), str(nums[p])]

for s in states:
    print(s[0].zfill(6)+s[1].zfill(6))

Solution (Python):
import copy
n,m = map(int, input().split())
town = [[] for _ in range(n+1)]
for i in range(m):
  p,y = map(int, input().split())
  town[p].append((i,y))
res = []
for i in range(1,n+1):
  tw = copy.copy(town[i])
  for j,x in enumerate(sorted(tw, key=lambda x: x[1])):
    res.append((x[0],str(i).zfill(6)+str(j+1).zfill(6)))

for x in sorted(res, key=lambda x: x[0]):
  print(x[1])

Solution (Python):
import numpy as np


def solve(string):

    n, m, *py = map(int, string.split())
    py = [(_p, _y) for _p, _y in zip(py[0::2], py[1::2])]
    p = [[] for _ in range(n)]
    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)]
    ans = []
    for _p, _y in py:
        ans.append("{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1))
        counter[_p - 1] += 1
    return "\n".join(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve("{} {}\n".format(n, m) + "\n".join([input() for _ in range(m)])))

Solution (Python):
import numpy as np


n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
p = [[] for _ in range(n)]
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):


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

city_tb_ = sorted(city_tb,key=lambda x:x[1])


count_cities = [0 for i in range(n+1)]
city_cla = {}
for i in range(m):
    count_cities[city_tb_[i][0]] += 1
    city_cla[str(city_tb_[i][0])+str(city_tb_[i][1])]='{:06d}'.format(city_tb_[i][0])+'{:06d}'.format(count_cities[city_tb_[i][0]])

for i in range(m):
    print(city_cla[str(P[i])+str(Y[i])])

Solution (Python):
import bisect

N,M=map(int,input().split())
lists=[list(map(int,input().split())) for _ in range(M)]
dict={}

for l in lists:
    if l[0] not in dict.keys():
        dict[l[0]]=[l[1]]
    else:
        dict[l[0]].append(l[1])

for d in dict.values():
    d.sort()

for l in lists:
    print(str(l[0]).zfill(6)+str(bisect.bisect_right(dict[l[0]],l[1])).zfill(6))

Solution (Python):


from sys import stdin

input = stdin.readline

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

Info = []

for i in range(M):
    s = input().split()
    Info.append([i, int(s[0]), int(s[1]), s[0], 'a'])
    while len(Info[i][3]) < 6:
        Info[i][3] = '0' + Info[i][3]

Info.sort(key=lambda x: (x[1],x[2]))

j = 0
k = Info[0][1]
for i in range(M):
    if k == Info[i][1]:
        j += 1
        Info[i][4] = str(j)
        while len(Info[i][4]) < 6:
            Info[i][4] = '0' + Info[i][4]
    else:
        k = Info[i][1]
        j = 1
        Info[i][4] = str(j)
        while len(Info[i][4]) < 6:
            Info[i][4] = '0' + Info[i][4]

Info.sort()

for i in range(M):
    print(Info[i][3] + Info[i][4])

Solution (Python):
def search(l,x):
    min_ = 0
    max_ = len(l) - 1
    k = int((min_+max_)/2)
    while(abs(min_-max_) > 1):
        if l[k] > x:
            max_ = k
        elif l[k] < x:
            min_ = k
        else:
            max_ = k
            min_ = k
            break

        k = int((min_+max_)/2)

    if l[max_] == x:
        return max_
    return min_



N,M = (int(i) for i in input().split())  

kens = []
ps = [0] * M
ys = [0] * M
for _ in range(N):
    kens.append([])
for i in range(M):
    p,y = (int(i) for i in input().split())
    ps[i] = p
    ys[i] = y
    kens[p-1].append(y)


kens_s = [0] * N
for i in range(N):
    kens_s[i] = sorted(kens[i])

for i in range(M):
    
    num = search(kens_s[ps[i]-1],ys[i]) + 1
    print('{0:06d}'.format(ps[i]) + '{0:06d}'.format(num))

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

p_c=[0]*N
p_y.sort(key=lambda x:x[2])
for k,a in enumerate(p_y):
    p_c[a[1]-1]+=1
    p_y[k].append(p_c[a[1]-1])
p_y.sort(key=lambda x:x[0])
for b in p_y:
    print(str(b[1]).zfill(6)+str(b[3]).zfill(6))

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

p_count=[0]*N
p_y.sort(key=lambda x:x[2])
for num,a in enumerate(p_y):
    p_count[a[1]-1]+=1
    p_y[num].append(p_count[a[1]-1])
p_y.sort(key=lambda x:x[0])
for b in p_y:
    print(str(b[1]).zfill(6)+str(b[3]).zfill(6))

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

class ID:
    def __init__(self,p,y,i):
        self.p = p
        self.y = y
        self.i = i
        self.ID1 = None
        self.ID2 = None

    def ID(self):
        for i in range(1,7):
            if self.ID1 < 10**i:
                self.ID1 = "0"*(6-i) + str(self.ID1)
                break
        for i in range(1,7):
            if int(self.ID2) < 10**i:
                self.ID2 = "0"*(6-i) + str(self.ID2)
                break
        
        return self.ID1 + self.ID2

cities = []
for i in range(0,M):
    P,Y = map(int,input().split())
    cities.append(ID(P,Y,i))
cities.sort(key = lambda x: x.y)
counter = [-1]

for i in range(0,N):
    counter.append(1)

for c in cities:
    c.ID1 = c.p
    c.ID2 = counter[c.p]
    counter[c.p] = counter[c.p] + 1

cities.sort(key = lambda x: x.i)

for i in range(0,M):
    print(cities[i].ID())

Solution (Python):
N, M = map(int, input().split())
dic = {}
cnt = [1]*N
for m in range(M):
  dic[m] = list(map(int, input().split()))
l = sorted([d for d in dic.items()], key=lambda x:x[1][1])
for m in range(len(l)):
  l[m][1].append(cnt[l[m][1][0]-1])
  cnt[l[m][1][0]-1] += 1
for d in dic.values():
  print("{:06d}{:06d}".format(d[0], d[2]))

Solution (Python):
n,m=map(int, input().split())
l=[]
for i in range(m):
    l.append(list(map(int, input().split())))
    l[i].append(i)
l.sort(key=lambda x:(x[0],x[1]))
t=1
l[0].append(str(l[0][0]).zfill(6)+str(1).zfill(6))
for i in range(1,m):
    if l[i][0]>l[i-1][0]:
        t=1
        l[i].append(str(l[i][0]).zfill(6)+str(1).zfill(6))
    else:
        t+=1
        l[i].append(str(l[i][0]).zfill(6)+str(t).zfill(6))

l.sort(key=lambda x:x[2])
for i in range(m):
    print(l[i][3])

Solution (Python):






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

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





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





num = 1

for i in range(m):
    if i == 0:
        data[i][1] = num
        num += 1
    else:
        if data[i][0] == data[i-1][0]:
            data[i][1] = num
            num += 1
        else:
            data[i][1] = 1
            num = 2





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





for i in range(m):
    p = str(data[i][0]).zfill(6)
    num = str(data[i][1]).zfill(6)
    print(p+num)

Solution (Python):
from collections import defaultdict
from bisect import bisect_left

N, M = map(int, input().split())
A = []
B = defaultdict(list)

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

for key in B.keys():
    B[key].sort()

for a in A:
    print("%06d%06d" % (a[0], bisect_left(B[a[0]], a[1])+1))

Solution (Python):
import numpy as np

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)

order = (np.array(Y)).argsort()
n_list = [0]*N
m_list = [0]*M
for i in order:
  n_list[P[i]-1]+=1
  m_list[i] = n_list[P[i]-1]
  
for i in range(M):
  l = len(str(P[i]))
  pi = "0"*(6-l)+str(P[i])
  lx = len(str(m_list[i]))
  x = "0"*(6-lx)+str(m_list[i])
  print(pi+x)

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

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


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



c = {}
newpy = []
for i in py:
    index = i[0]
    ken = i[1]
    year = i[2]
    if ken in c:
        c[ken] += 1
        order = c[ken]
    else:
        c[ken] = 1
        order = 1
    newpy.append((index, ken, order))


newpy.sort(key=lambda tup: tup[0])

for i in newpy:
    print("{:0=6}{:0=6}".format(i[1], i[2]))

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

cur = 1
cnt = 1
for i in range(M):
    if A[i][0] == cur:
        A[i].append(cnt)
        cnt += 1
    else:
        cur = A[i][0]
        cnt = 1
        A[i].append(cnt)
        cnt += 1
A.sort(key=lambda x: x[2])

for a in A:
    print("%06d%06d" % (a[0], a[3]))

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

inputs = sorted(inputs, key = lambda i:i[2])
count = [0 for i in range(n)]
for i in inputs:
  count[i[1]-1] += 1
  i[3] = count[i[1]-1]

inputs = sorted(inputs, key = lambda i:i[0])

for i in inputs:
  print('{0[1]:06}{0[3]:06}'.format(i))

Solution (Python):
N,M = list(map(int,input().split()))
l=[]
for i in range(M):
    l.append(list(map(int,input().split())))
for j in range(M):
    l[j].append(j)
l.sort(key=lambda x:(x[0],x[1]))

l[0].append(1)
for k in range(1,M):
    if l[k][0] == l[k-1][0]:
        l[k].append(l[k-1][3]+1)
    else:
        l[k].append(1)

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

for m in range(M):
    s='00000' + str(l[m][0])
    t='00000' + str(l[m][3])
    print(s[len(s)-6:len(s)]+t[len(t)-6:len(t)])

Solution (Python):
n, m = map(int, input().split())
tmp = [list(map(int, input().split())) for i in range(m)]
city = [[] for i in range(n+1)]
answers = [''] * m

for i, (pref, year) in enumerate(tmp):
    city[pref].append([year, i])

for i in range(n+1):
    for j, (year, index) in enumerate(sorted(city[i])):
        ans = str(i).zfill(6) + str(j+1).zfill(6)
        answers[index] = ans

print(*answers, sep='\n')

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


for i,(pref,year) in enumerate(tmp):
    cities[pref].append([year,i])
    
answers = [""] * m
for i in range(n+1):
    for j,(year,index) in enumerate(sorted(cities[i])):
        answer = str(i).zfill(6) + str(j+1).zfill(6)
        answers[index] = answer
        
print(*answers,sep=("\n"))

Solution (Python):
n,m=map(int,input().split())
ken=[[] for i in range(n)]
for i in range(m):
    p,y=map(int,input().split())
    ken[p-1].append([i,y])
for i in range(n):
    ken[i].sort(key=lambda x:x[1])
ken0=[]
for i in range(n):
    for j in range(len(ken[i])):
        mae=str(i+1)
        ato=str(j+1)
        while len(mae)<6:
            mae='0'+mae
        while len(ato)<6:
            ato='0'+ato
        ken0.append([ken[i][j][0],mae+ato])
ken0.sort(key=lambda x:x[0])
for i in ken0:
    print(i[1])

Solution (Python):
n, m = [int(v) for v in input().split()]
cities = []
for i in range(m):
        py = tuple(int(v) for v in input().split())
        cities.append((py[1], py[0], i))
cities.sort()
nums = [None] * m
city_nums = {}
for city in cities:
        if not city[1] in city_nums:
                city_nums[city[1]] = 1
        else:
                city_nums[city[1]] += 1
        nums[city[2]] = str(city[1]).zfill(6) + str(city_nums[city[1]]).zfill(6)
for num in nums:
        print(num)

Solution (Python):
N,M = map(int, input().split())
pref = {}
city = [0] * M

for i in range(M):
    P,Y = map(int, input().split())
    if P not in pref.keys():
        pref[P] = []
    pref[P].append([i,Y])

for p in pref.keys():
    pref[p].sort(key=lambda e:e[1])
    for i,e in enumerate(pref[p]):
        city[e[0]] = '%06d%06d' % (p, i+1)

for c in city:
    print(c)

Solution (Python):
n, m = map(int, input().split())
city = []
for i in range(m):
    p, y = map(int, input().split())
    city.append([p,y,i])
city.sort(key = lambda x: x[1])
city.sort()
num = 1
for i in range(m):
    if i == 0:
        city[i][1] = num
        num += 1
    else:
        if city[i][0] == city[i-1][0]:
            city[i][1] = num
            num += 1
        else:
            city[i][1] = 1
            num = 2
city.sort(key = lambda x: x[2])
for i in range(m):
    p = format(city[i][0], '0>6')
    num = format(city[i][1], '0>6')
    print(p, end='')
    print(num)

Solution (Python):
N, M = map(int, input().split())
query_pairs = []
prefs = {}
for i in range(M):
    p, y = map(int, input().split())
    query_pairs.append([p, y])
    if p in prefs:
        prefs[p].append(y)
    else:
        prefs[p] = [y]

prefs_with_year_order = {}
for pref, years in prefs.items():
    years.sort()
    prefs_with_year_order[pref] = {}
    for i in range(len(years)):
        prefs_with_year_order[pref][years[i]] = i + 1 

for p, y in query_pairs:
    pref_part = "{0:06d}".format(p)
    order_part = "{0:06d}".format(prefs_with_year_order[p][y])
    print(pref_part + order_part)

Solution (Python):
from operator import itemgetter
pres = []
numbers = []
N,M = map(int, input().split())

for i in range(M):
    numbers.append('')

for i in range(N):
    pres.append([])

i = 0
for t in range(M):
    p,y = map(int,input().split())
    pres[p-1].append((y,i))
    i+=1

i = 0
for p in pres:
    i+=1
    if p==[]:
        continue
    front = '00000' + str(i)
    front = front[-6:]
    temp_p = p
    temp_p.sort(key=itemgetter(0))
    j = 0
    for city in temp_p:
        j+=1
        back = '00000' + str(j)
        back = back[-6:]
        numbers[city[1]] = front+back
        
for num in numbers:
    print(num)

Solution (Python):
n,m = map(int,input().split())
city = [[] for i in range(n)]
def f(s):
    s = str(s)
    t  = 6 - len(s)
    s = "0"*t + s
    return s
for i in range(m):
    ken,year = map(int,input().split())
    city[ken-1].append([year,i])
newcity = []
for i in range(n):
    city[i].sort()
    for j in range(len(city[i])):
        newcity.append([city[i][j][1],f(i+1) + f(j+1)])
newcity.sort()
for i in range(m):
    print(newcity[i][1])

Solution (Python):
N, M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    p, y = [int(i) for i in input().split()]
    data.append([i, p, y])
data.sort(key=lambda x:(x[1],x[2]))
ind = 1
for j, (i, p, y) in enumerate(data):
    if (data[j-1][1] != p) and (j > 0):
        ind = 1
    data[j].append(ind)
    ind += 1
data.sort(key=lambda x:x[0])
for i, p, y, j in data:
    print(str(p).zfill(6) + str(j).zfill(6))

Solution (Python):
N, M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    p, y = [int(i) for i in input().split()]
    data.append([i, p, y])
data.sort(key=lambda x:(x[1],x[2]))
ind = 1
for j, (i, p, y) in enumerate(data):
    if data[j-1][1] != p:
        ind = 1
    data[j].append(ind)
    ind += 1
data.sort(key=lambda x:x[0])
for i, p, y, j in data:
    print(str(p).zfill(6) + str(j).zfill(6))

Solution (Python):
n, m = [int(i) for i in input().split(" ")]
ps = []
pc = [0 for i in range(0, n + 1)]

for i in range(0, m):
    ps.append([i] + [int(i) for i in input().split(" ")] + [""])

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

for i in range(0, m):
    pc[ps[i][1]] += 1
    ps[i][3] = str(ps[i][1]).zfill(6) + str(pc[ps[i][1]]).zfill(6)

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

for i in range(0, m):
    print(ps[i][3])

Solution (Python):
n, m = map(int, input().split())
no = 0
l = []
ans = []

cityNo = 0

beforeKen = 0

for i in range(m):
    p, y = map(int, input().split())
    l.append([p, y, no])
    no += 1

l.sort()

for j in l:
    if j[0] == beforeKen:
        cityNo += 1
    else:
        cityNo = 1

    ans.append([j[2], str(j[0]).zfill(6) + str(cityNo).zfill(6)])
    beforeKen = j[0]

ans.sort()

for k in ans:
    print(k[1])

Solution (Python):
N,M = map(int,input().split())
L = []
for i in range(M):
  L.append(list(map(int,input().split())))
for j in range(M):
  L[j].append(j)
L.sort()
l = L[0][0]
cnt = 0
for k in range(M):
  if l == L[k][0]:
    cnt += 1
    L[k].append(cnt)
  else:
    l = L[k][0]
    cnt = 1
    L[k].append(cnt)
L = sorted(L, key = lambda x:x[2])
for i in range(M):
  print('0'*(6-len(str(L[i][0])))+str(L[i][0])+'0'*(6-len(str(L[i][3])))+str(L[i][3]))

Solution (Python):


import math
import sys
import heapq
from operator import itemgetter
input = sys.stdin.readline











cities = dict()
N, M = map(int, input().rstrip().split())
for i in range(M):
	p, y = map(int, input().rstrip().split())
	if p not in cities:
		cities[p] = [[i, y]]
	else:
		cities[p].append([i, y])

heap_q = []	
for i in cities:
	tmp = sorted(cities[i], key=lambda x: x[1])
	for j in range(len(tmp)):
		heapq.heappush(heap_q, (tmp[j][0], i, j+1))

for i in range(M):
	x, y, z = heapq.heappop(heap_q)
	print(str(y).zfill(6) + str(z).zfill(6))

Solution (Python):
n, m = map(int, input().split())
t = []
for i in range(m):
    p,y = map(int, input().split())
    t.append([p, y, i])
target = sorted(t)
target[0].append(1)
cnt = 1
for i in range(1,m):
    if target[i][0]!=target[i-1][0]:
        cnt = 1
    else:
        cnt += 1
    target[i].append(cnt)
ans = sorted(target, key=lambda x:x[2])
for i in range(m):
    print(str(ans[i][0]).zfill(6) + str(ans[i][3]).zfill(6))

Solution (Python):
def main():
    N, M = list(map(int, input().split()))
    cityList = {}
    for i in range(M):
        P, Y = list(map(int, input().split()))
        if not P in cityList:
            cityList[P] = [[i, Y]]
        else:
            cityList[P].append([i, Y])
    for value in cityList.values():
        value.sort(key=lambda city: city[1])
    cityNumList = []
    for key, value in cityList.items():
        for i in range(len(value)):
            cityNumList.append([value[i][0], "{:06d}{:06d}".format(key, i+1)])
    cityNumList.sort(key=lambda city: city[0])
    for cityNum in cityNumList:
        print(cityNum[1])

if __name__ == "__main__":
    main()

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

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

count=[0]*N
ans=[]

for i in data:
    count[i[0][0]-1] += 1
    ans.append([i[1],str(i[0][0]).zfill(6) + str(count[i[0][0]-1]).zfill(6)])

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

for i in ans:
    print(i[1])

Solution (Python):
def read():
    return int(input())

def reads():
    return list(map(int, input().split()))

n,m = reads()
cnt = {k:[] for k in range(n+1)}
buf = [None]*m
for i in range(m):
    p,y = reads()
    cnt[p].append((y,i))
for p,l in cnt.items():
    if not l:
        continue
    l.sort()
    for j,(y,i) in enumerate(l):
        buf[i] = '{:06d}{:06d}'.format(p,j+1)

print('\n'.join(buf))

Solution (Python):
import numpy as np

N,M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
order = [[] for _ in range(N)]
for p,y in X:
    order[p-1].append(y)

for i in range(N):
    order[i] = np.argsort(np.argsort(order[i]))
cnts = [0 for _ in range(N)]
for i in range(M):
    p = X[i][0]
    print('{:06}{:06}'.format(p, order[p-1][cnts[p-1]]+1) )
    cnts[p-1] += 1

Solution (Python):


N, M = map(int, input().split())
c_l = [[int(i) for i in input().split()] + [j] for j in range(M)]


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

counter = [0] * (N+1)
for c in c_l:
    p = c[0]
    counter[p] += 1
    c.append("{:06}{:06}".format(c[0], counter[p]))

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

for c in c_l:
    print(c[3])

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

ken = [(i,) + tuple(map(int,input().split())) for i in range(m)]

def func(elem):
    return elem[1:3]
ken.sort(key=func)

currKen = ken[0][1]
cnt = 1
for i in range(len(ken)):
    if ken[i][1] == currKen:
        ken[i] +=(cnt,)
        cnt += 1
    else:
        currKen = ken[i][1]
        cnt = 1
        ken[i] +=(cnt,)
        cnt += 1



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

for k in ken:
    print("%.6d%.6d"%(k[1],k[3]))

Solution (Python):

N, M = map(int, input().split())
X = [[int(i) for i in input().split()] + [j] for j in range(M)]
X.sort(key=lambda x: x[1])

Num = [0]*(N+1)

for i in range(M):
    p = X[i][0]
    Num[p] += 1
    c = Num[p]
    X[i].append(str(p).zfill(6) + str(c).zfill(6))

X.sort(key=lambda x: x[2])
for i in range(M):
    print(X[i][3])

Solution (Python):
N,M = map(int,input().split())
L = []
for i in range(M):
    l = list(map(int,input().split()))+[i]
    L.append(l)
cnt = 0
tmp = []
M = sorted(L,key = lambda x: (x[0],x[1]))
for x in M:
    if tmp == x[0]:
        x.append(cnt+1)
        cnt += 1
    else:
        tmp = x[0]
        cnt = 0
        x.append(cnt)
M = sorted(L,key = lambda x:x[2])

for x in M:
    st = str(x[0]).zfill(6)
    st += str(x[3]+1).zfill(6)
    print(st)

Solution (Python):
N,M = map(int,input().split())
L = []
for i in range(M):
    l = list(map(int,input().split()))+[i]
    L.append(l)
cnt = 0
tmp = []
M = sorted(L,key = lambda x: (x[0],x[1]))
for x in M:
    if tmp == x[0]:
        x.append(cnt+1)
        cnt += 1
    else:
        tmp = x[0]
        cnt = 0
        x.append(cnt)
M = sorted(L,key = lambda x:x[2])

for x in M:
    st = str(x[0]).zfill(6)
    st += str(x[3]+1).zfill(6)
    print(st)

Solution (Python):
from collections import defaultdict

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

city = []

for i in range(M):
    P, Y = map(int, input().split())
    city.append([i, P, Y])
city.sort(key=lambda x: x[2])

count = defaultdict(lambda: 0)
for c in city:
    count[c[1]] += 1
    c.append(count[c[1]])
city.sort(key=lambda x: x[0])

for _, P, _, n in city:
    print(format(P, '06') + format(n, '06'))

Solution (Python):
def main() -> None:
    N, M = map(int, input().split())
    PYT = [tuple(map(int, input().split())) for _ in range(M)]
    PYTS = sorted(PYT)

    before = 0
    tmp = {}
    for py in PYTS:
        if before != py[0]:
            
            before = py[0]
            count = 0
        count += 1
        tmp[py] = count

    for py in PYT:
        print("{:06}{:06}".format(py[0], tmp[py]))


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
Y = sorted([(i, (p, y)) for i, (p, y) in enumerate(L)], key=lambda x: x[1])
result = [""] * M
x = 0
before_p = 0
for i, (p, y) in Y:
    if before_p != p:
        x = 0
        before_p = p
    x += 1
    result[i] = "{:06}{:06}".format(p, x)
for r in result:
    print(r)

Solution (Python):
r=lambda i:('0'*6+str(i))[-6:]
I=lambda:map(int,input().split())
N,M=I()
C=[[i]+list(I())for i in range(M)]
C=sorted(C,key=lambda x:(x[1],x[2]))
q=1;c=1;l=[]
for i,p,_ in C:q,c=(p,1)if p>q else (q,c);l+=[[i,r(p)+r(c)]];c+=1
for _,s in sorted(l,key=lambda x:(x[0])):print(s)

Solution (Python):
N, M = map(int, input().split())
PY = [tuple(map(int,input().split())) for i in range(M)]

PY_sort = sorted(PY)

tmp = dict()

before = 0
for py in PY_sort:
    if before != py[0]:
        before = py[0]
        count = 0
    count += 1
    tmp[py] = count

for py in PY:
    print("{:06}{:06}".format(py[0],tmp[py]))

Solution (Python):
from bisect import bisect_left
n,m=map(int,input().split())
ls=[[] for i in range(n)]
py=[]
for i in range(m):
  p,y=map(int,input().split())
  ls[p-1].append(y)
  py.append([p,y])
ls=list(map(lambda x:sorted(x),ls))
for i in range(m):
  p,y=py[i]
  index= bisect_left(ls[p-1],y)
  print(str(p).zfill(6)+str(index+1).zfill(6))

Solution (Python):
def inpl(): return list(map(int, input().split()))
N, M = inpl()
A = [""]*M
P = [[] for _ in range(N+1)]
for i in range(M):
    p, y = inpl()
    P[p].append((y, i))

for p, prefecture in enumerate(P):
    prefecture = sorted(prefecture, key=lambda x: x[0])
    for j, (y, i) in enumerate(prefecture):
        A[i] = "{}{}".format(str(p).zfill(6), str(j+1).zfill(6))

print(*A, sep="\n")

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

cities = {}
prefs = []

for i in range(1, M + 1):
  p, y = list(map(int, input().split()))
  
  pref = {"city": p, "year": y}
  prefs.append(pref)

  if p not in cities:
    cities[p] = [pref]
  else:
    cities[p].append(pref)

for city in cities.values():
  city.sort(key=lambda p: p['year'])
  for idx, pref in enumerate(city):
    pref['pref_id'] = str(idx + 1).zfill(6)

[print("%s%s" % (
  str(int(pref['city'])).zfill(6), 
  pref['pref_id'])) for pref in prefs]

Solution (Python):
n,m=list(map(int,input().split(" ")))
py=[]
for i in range(m):
    py.append(list(map(int,input().split(" ")))+[i])
py.sort()
ids = []
c=1
p=1
for j in py:
    if j[0] != p:
        c=1
        p=j[0]
    ids.append([j[2],"{:0>6}{:0>6}".format(j[0],c)])
    c+=1
ids.sort()
for i in ids:
    print(i[1])

Solution (Python):
n, m = list(map(int, input().split()))
li = []
yli = []
for _ in range(m):
    p, y = list(map(int, input().split()))
    li.append((y, p))
    yli.append(y)

import numpy as np
idx = np.argsort(yli).argsort()
srt = sorted(li)
ans = []
from collections import Counter
pcnt = Counter()
for y, p in srt:
    pcnt[p] += 1
    ans.append('{:06}{:06}'.format(p, pcnt[p]))

for i in idx:
    print(ans[i])

Solution (Python):
N, M = map(int,input().split())
PY = [list(map(int,input().split()))+[0] for _ in range(M)]
sort_PY = sorted(PY, key = lambda x: x[1])
city = {}
for py in sort_PY:
  if(py[0] in city):
    city[py[0]] += 1
  else:
    city[py[0]] = 1
  py[2] = city[py[0]]
for py in PY:
  print(str(py[0]).zfill(6) + str(py[2]).zfill(6))

Solution (Python):
n,m = map(int,input().split())
l = []
for i in range(m):
    l.append([i]+list(map(int, input().split())))
l = sorted(l, key=lambda x:(x[1],x[2]))
ind = 0
id = []
for i in range(n):
    nature = i+1
    j = 1
    while ind<len(l) and l[ind][1]==nature:
        id.append([l[ind][0],nature,j])
        j+=1
        ind+=1
id = sorted(id, key=lambda x:x[0])
for i in range(len(id)):
    print('{:0=6}'.format(id[i][1])+'{:0=6}'.format(id[i][2]))

Solution (Python):
N, M = map(int, input().split())
L = []
P = [0]*(N+1)
for i in range(M):
    p, y = map(int, input().split())
    L.append([i, p, y, 0])

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

for l in L:
    P[l[1]] += 1
    l[3] = P[l[1]]    
        
for l in sorted(L, key = lambda x:x[0]):
    print('{0:0>6d}{1:0>6d}'.format(l[1], l[3]))

Solution (Python):
a,b=map(int,input().split())
L=[[] for i in range(a)]
u=0

for i in range(b):
    u+=1
    c=list(map(int,input().split()))
    c.append(u)
    L[int(c[0])-1].append(c)

for i in L:
    i.sort(key=lambda x:x[1])

for i in L:
    e=0
    for j in i:
        e+=1
        j.append(e)
q=[]
for w in L:
   q.extend(w)

q.sort(key=lambda x:x[2])
for r in range(b):
        print(str(q[r][0]).zfill(6)+str(q[r][3]).zfill(6))

Solution (Python):
a,b=map(int,input().split())
L=[[] for i in range(a)]
u=0
for i in range(b):
    u+=1
    c=list(map(int,input().split()))
    c.append(u)
    L[int(c[0])-1].append(c)
for i in L:
    i.sort(key=lambda x:x[1])
for i in L:
    e=0
    for j in i:
        e+=1
        j.append(e)
q=[]
for w in L:
   q.extend(w) 
q.sort(key=lambda x:x[2])
for r in range(b):
        print(str(q[r][0]).zfill(6)+str(q[r][3]).zfill(6))

Solution (Python):
a,b=map(int,input().split())
L=[[] for i in range(a)]
u=0
for i in range(b):
    u+=1
    c=list(map(int,input().split()))
    c.append(u)
    L[int(c[0])-1].append(c)
for i in L:
    i.sort(key=lambda x:x[1])
for i in L:
    e=0
    for j in i:
        e+=1
        j.append(e)
q=[]
for w in L:
   q.extend(w) 
q.sort(key=lambda x:x[2])
for r in range(b):
        print('0'*(6-len(str(q[r][0])))+str(q[r][0])+'0'*(6-len(str(q[r][3])))+str(q[r][3]))

Solution (Python):
N, M = map(int, input().split())
ken = [[] for i in range(N)]
Y = []
for i in range(M):
    p, y = map(int, input().split())
    Y.append(y)
    ken[p-1].append(i)

for i in range(len(ken)):
    ken[i].sort(key=lambda x: Y[x])


ans = ["0"] * M
for i in range(len(ken)):  
    for j in range(len(ken[i])):  
        ans[ken[i][j]] = str(i+1).zfill(6) + str(j+1).zfill(6)
for a in ans:
    print(a)