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 heapq


def make_ans(str1, str2):
    while len(str1) < 6:
        str1 = '0' + str1
    while len(str2) < 6:
        str2 = '0' + str2
    return str1 + str2


n, m = map(int, input().split())
ken = [[] for _ in range(n + 1)]


memo = []
for i in range(1, m + 1):
    p, y = map(int, input().split())
    ken[p].append(y)
    memo.append((p, y))
for i in range(1, n + 1):
    ken[i].sort()

for q in memo:
    ans_left = str(q[0])
    begin = 0
    end = len(ken[q[0]]) - 1
    ans_index = -1
    mid = 0
    while True:
        
        
        mid = (end + begin) // 2
        if ken[q[0]][mid] > q[1]:
            end = mid
        elif ken[q[0]][mid] < q[1]:
            begin = mid
        else:
            ans_index = mid
            break
        if ken[q[0]][end] == q[1]:
            ans_index = end
            break
        elif ken[q[0]][begin] == q[1]:
            ans_index = begin
            break
    ans_right = str(ans_index + 1)
    print(make_ans(ans_left, ans_right))

Solution (Python):
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

for i in range(m):
    ab[i].append(i)

ab_l = sorted(ab, key=lambda x: x[1])
ab_ll = sorted(ab_l, key=lambda x: x[0])

temp = 1
for j in range(m):
    if j==0 or ab_ll[j][0] != ab_ll[j-1][0]:
        temp = 1
    else:
        temp +=1
    ab_ll[j].append(temp)

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

for i in range(m):
    print(str(ab_lll[i][0]).zfill(6)+str(ab_lll[i][3]).zfill(6))

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



ipy=[]

for i in range(m):
    ipy.append(list(map(int,(str(i) + " " + input()).split())))

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

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

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

for i in range(m):
    print(f'{ipy[i][1]:06}'+f'{ipy[i][2]:06}')

Solution (Python):

N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

res = [""] * M
ctr = [0] * (N + 1)
for i, (p, y) in sorted(enumerate(X), key=lambda x: (x[1][0], x[1][1])):
    ctr[p] += 1
    res[i] = "{:0>6}{:0>6}".format(p, ctr[p])

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

Solution (Python):
from bisect import bisect_left
n,m = map(int, input().split())

l = [[] for _ in range(n)]
city = []
for i in range(m):
  p,y = map(int, input().split())
  city.append([p,y])
  l[p-1].append(y)

for i in l: i.sort()
for i in city:
  ans = ""
  ans += "0"*(6-len(str(i[0])))+str(i[0])
  t = str(bisect_left(l[i[0]-1], i[1]) + 1)
  ans += "0"*(6-len(t))+t
  print(ans)

Solution (Python):
n, m = list(map(int, input().split()))
ps = [[] for _ in range(n)]

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

for i in range(n):
    ps[i] = sorted(ps[i])

    pstr = str(i+1).zfill(6)

    for j in range(len(ps[i])):
        ps[i][j] = (pstr + str(j+1).zfill(6), ps[i][j][1])

ps = [city for sub in ps for city in sub]
ps = sorted(ps, key = lambda x: x[1])

for city in ps:
    print(city[0])

Solution (Python):

from bisect import *

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

d = [[] for _ in range(n)]
for i in range(m):
    d[p[i]-1].append(y[i])

for i in range(len(d)):
    d[i] = sorted(d[i])

ls = rs = ''
def complement(nstr):
    while len(nstr) != 6:
        nstr = '0' + nstr
    return nstr

for i in range(m):
    ls = complement(str(p[i]))
    r = bisect_right(d[p[i]-1], y[i])
    rs = complement(str(r))
    ans = ls+rs
    print(ans)

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

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

a = P[0][0]
c = 0
for i in range(M):
    
    if P[i][0] == a:
        c += 1
        P[i].append(c)
    else:
        c = 1
        a = P[i][0]
        P[i].append(c)
    

P = sorted(P, key = lambda x: x[2])
for i in range(M):
    s = str(P[i][0]).zfill(6)
    ss = str(P[i][3]).zfill(6)
    print(s + ss)

Solution (Python):
def main():
    import bisect
    n,m = map(int,input().split())
    d = [[] for i in range(n)]
    ans = [0 for i in range(m)]
    for i in range(m):
        p,y = map(int,input().split())
        d[p-1].append((y,i))
    for i,d_ in enumerate(d):
        d_.sort()
        for c, d__ in enumerate(d_):
            ans[d__[1]] = str(i+1).zfill(6) + str(c+1).zfill(6)
    for i in range(m):
        print(ans[i])

if __name__ == "__main__":
    main()

Solution (Python):
N,M = map(int,input().split())
D = [[]for _ in range(N)]

for i in range(M):
    p,y = map(int,input().split())
    D[p-1].append((y,i))
ans = [0]*M


for i,d in enumerate(D):
    
    d.sort()
    for k,(y,j)in enumerate(d):
        
        ans[j]=str(i+1).zfill(6)+str(k+1).zfill(6)

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

Solution (Python):
from sys import stdin

n,m = map(int,input().split())
cities = [list(map(int,stdin.readline().split())) + [i] for i in range(m)]
for i in range(m):
    cities[i][0] -= 1
state = [[] for i in range(n)]
for i in cities:
    state[i[0]].append([i[1],i[2]])
for i in range(n):
    state[i].sort()
ans = []
for i in range(n):
    temp = "0"*(6-len(str(i+1))) + str(i+1)
    for j in range(len(state[i])):
        s = temp + "0"*(6-len(str(j+1))) + str(j+1)
        ans.append([state[i][j][1],s])
ans.sort()
for i in ans:
    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)]
 
di = defaultdict(list)
 
for i, py in enumerate(PY):
    di[py[0]].append([py[1], i])
 
ans = ["" for _ in range(M)]
 
for k, v in di.items():
    v.sort()
 
    for j, yi in enumerate(v):
        s = str(k).zfill(6)
        t = str(j + 1).zfill(6)
        ans[yi[1]] = s + t
 
print("\n".join(ans))

Solution (Python):

import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, m = MI()
    cities = []
    prefes = [1]*(n+1)
    for i in range(m):
        a, b = MI()
        cities.append([b, a,  i])

    cities.sort()

    for i in range(m):
        city = cities[i]
        pref = city[1]
        pref_id = str(pref).zfill(6)
        sequence_id = str(prefes[pref]).zfill(6)
        prefes[pref] += 1
        res_id = pref_id + sequence_id
        cities[i].append(res_id)

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

    for i in range(m):
        print(cities[i][-1])


main()

Solution (Python):
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():

    N, M = NMI()
        
    PY = [[m,NLI()] for m in range(M)]
    
    PY = list(sorted(list(sorted(PY,key = lambda x : x[1][1])),key = lambda x : x[1][0]))
    

    
    city = PY[0][1][0]
    cnt = 0

    for m in range(M):
        if PY[m][1][0] == city:
            cnt += 1
        else:
            city = PY[m][1][0]
            cnt = 1
            
        PY[m][1] = str(PY[m][1][0]).zfill(6) + str(cnt).zfill(6)
    
    PY = list(sorted(PY))
    
    
    for m in range(M):
        print(PY[m][1])


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
PY=[list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    PY[i].append(i)
py=sorted(PY)
ans=[None]*m

tmp_y=1
for i in range(m):
    if i>0:
        if py[i][0]!=py[i-1][0]:
            tmp_y=1
        else:
            tmp_y+=1
    ans_l="0"*(6-len(str(py[i][0])))+str(py[i][0])
    ans_r="0"*(6-len(str(tmp_y)))+str(tmp_y)
    
    ans[py[i][2]]=ans_l+ans_r
[print(i) for i in ans]

Solution (Python):
from collections import defaultdict
from bisect import bisect
n,m=map(int,input().split())
l=[tuple(map(int,input().split())) for _ in range(m)]
a=defaultdict(list)
for x,y in sorted(l):
    a[x]+=[y]

for x,y in l:
    z=bisect(a[x],y)
    print('%06d%06d'%(x,z))

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


citylis=[[] for i in range(n)]
for i in range(1,m+1):
  pi,yi=map(int,input().split())
  citylis[pi-1].append([i,yi])

for i in range(n):
  if len(citylis[i])!=0:
    citylis[i].sort(key=lambda x:x[1])

lis=[]
for i in range(n):
  for j in range(len(citylis[i])):
    cityposi=str(i+1)
    cityposi="0"*(6-len(cityposi))+cityposi
    ordernum=str(j+1)
    ordernum="0"*(6-len(ordernum))+ordernum
    lis.append([citylis[i][j][0],cityposi+ordernum])

lis.sort(key=lambda x:x[0])
for i in range(m):
  print(lis[i][1])

Solution (Python):
N, M = map(int, input().split())
D = [[] for _ in range(N)]
R = [0]*M
for i in range(M):
    P, Y = map(int, input().split())
    D[P-1].append((Y,i))
for P in range(N):
    for k, p in enumerate(sorted(D[P])):
        Y, i = p
        R[i] = (P+1)*10**6+(k+1)
for r in R:
    print("{:012}".format(r))

Solution (Python):
from operator import itemgetter

n, m = map(int, input().split())
yp = []
for i in range(m):
  p_, y_ = map(int, input().split())
  yp.append([y_, p_, i+1])
py = sorted(yp)
ken = [0]*n
res = []
for i in range(m):
  ken[py[i][1]-1] += 1
  p, q, r = py[i][1], ken[py[i][1]-1], py[i][2]
  res.append([p, q, r])



res.sort(key=itemgetter(2))

for i in range(m):
  ans1 = [0]*(6-len(str(res[i][0])))
  ans1.append(res[i][0])
  ans2 = [0]*(6-len(str(res[i][1])))
  ans2.append(res[i][1])
  print(*ans1, *ans2, sep='')

Solution (Python):
import sys


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    results = {}
    p_list = []
    y_list = []
    cnt = 0
    for i in range(m):
        p, y = map(int, input().split())
        p_list.append(p)
        y_list.append(y)
        if results.get(p) is None:
            results[p] = [y]
        else:
            results[p].append(y)
    for i, p in results.items():
        p_sorted = sorted(p)
        results[i] = p_sorted

    for i, p in enumerate(p_list):
        import bisect
        print('{:006}'.format(p) + '{:006}'.format(bisect.bisect_left(results[p], y_list[i]) + 1))


if __name__ == "__main__":
    main()

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

PY_sorted = sorted(PY, key=lambda a: (a[0], a[1]))
PY_sorted[0][3] = str(PY_sorted[0][0]).zfill(6) + str(1).zfill(6)

cnt = 1
for i in range(1, M):
    cnt += 1
    if PY_sorted[i][0] != PY_sorted[i - 1][0]:
        cnt = 1
        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)
    else:
        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)

ans = sorted(PY_sorted, key=lambda a: a[2])
for a in ans:
    print(a[3])

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

dic = {i:[(0,0)] for i in range(1,N+1)}
lst = ['']*M

for i in range(M):
  p,y = map(int, input().split())
  dic[p].append((y,i))
  
for k in dic:
  dic[k].sort(key=lambda x:x[0])
  for i in range(1,len(dic[k])):
    lst[dic[k][i][1]] = str(k).zfill(6)+str(i).zfill(6)
    
for l in lst:
  print(l)

Solution (Python):
import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict


MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

def Main():
    n, m = read_ints()
    py = []
    for i in range(m):
        p, y = read_ints()
        py.append([y, p, i])
    py.sort(key=lambda x: x[0])  
    cnt = [0] * n
    ans = [''] * m
    
    for year, prefecture, idx in py:
        cnt[prefecture - 1] += 1
        ans[idx] = f'{prefecture:06d}{cnt[prefecture-1]:06d}'

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

if __name__ ==  '__main__':
    Main()

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

py.sort(key=lambda x:x[0]*10**6+x[1])
ne=[1]*(10**5+1)
ans=[]

for p,_,i in py:
    ans.append((str(p).zfill(6)+str(ne[p]).zfill(6),i))
    ne[p]+=1

ans.sort(key=lambda x:x[1])
for s,_ in ans:
    print(s)

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

N, M = map(int, input().split())
p = [tuple(map(int, input().split())) for _ in range(M)]
a = defaultdict(list)
for x, y in sorted(p):
    a[x] += [y]

for x, y in p:
    z = bisect(a[x], y)
    print("%06d%06d"%(x, z))

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

order = [[] for i in range(n + 1)]
id_perf_map = [-1 for i in range(m + 1)]

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

id_num_map = [-1 for i in range(m + 1)]

for i in range(1, n + 1):
    order[i] = list(sorted(order[i], key=lambda x: x[1]))
    for idx, (city_id, _) in enumerate(order[i]):
        id_num_map[city_id] = idx + 1

for i in range(1, m + 1):
    print('{:06}{:06}'.format(id_perf_map[i], id_num_map[i]))

Solution (Python):
from collections import defaultdict


N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]

di = defaultdict(list)

for i, py in enumerate(PY):
    di[py[0]].append([py[1], i])

ans = ["" for _ in range(M)]

for k, v in di.items():
    v.sort()

    for j, yi in enumerate(v):
        s = str(k).zfill(6)
        t = str(j + 1).zfill(6)
        ans[yi[1]] = s + t

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

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()
city = [[] for i in range(N+1)]
for i in range(M):
    P,Y = MI()
    city[P].append((Y,i))

ID = []
for i in range(N+1):
    city[i] = sorted(city[i])
    for j in range(len(city[i])):
        P,Y = city[i][j]
        ID.append((Y,str(i).zfill(6)+str(j+1).zfill(6)))

ID.sort()
for i in range(M):
    print(ID[i][1])

Solution (Python):
n,m=map(int, input().split())
alist=[]
for i in range(m):
  p,y=map(int, input().split())
  alist.append([i+1,p,y])
alist.sort(key=lambda x: x[2])
blist=[0]*(n+1)
ans=[0]*m
for i in range(m):
  blist[alist[i][1]]+=1
  ans1='0'*(6-len(str(alist[i][1])))
  ans2=str(alist[i][1])
  ans3='0'*(6-len(str(blist[alist[i][1]])))
  ans4=str(blist[alist[i][1]])
  ans[alist[i][0]-1]=ans1+ans2+ans3+ans4
for i in range(m):
  print(ans[i])

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

c = [0] * (n+1)

py = []

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

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

a = [""] * m

for p, y, i in py:
    c[p] += 1
    x = c[p]
    z = str(p * 1000000 + x)
    
    if len(z) < 12:
        a[i] = "0" * (12-len(z)) + z
    else:
        a[i] = z

for x in a:
    print(x)

Solution (Python):
n,m=list(map(int,input().split()))
pre=[[] for i in range(n)]
pre_num=[[] for i in range(n)]
city=[]

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

from bisect import bisect_right

for i in range(n):
  town=sorted(pre[i])
  for j in range(len(town)):
    pre_num[i].append(bisect_right(town,pre[i][j]))

cnt=[0 for i in range(n)]
for i in city:
  print(str(i+1).zfill(6)+str(pre_num[i][cnt[i]]).zfill(6))
  cnt[i]+=1

Solution (Python):
n,m = map(int,input().split())
L = []
for i in range(m):
    li = list(map(int,input().split()))
    L.append(li)

li = []
for i,j in enumerate(L):
    li.append(j+[i])
li.sort(key = lambda x:(x[0],x[1]))

li.append([0,0,0])

k,r = li[0][0],1
for i in range(m):
    if li[i][0] == k:
        if li[i+1][1] == li[i][1]:
            li[i][1] = r
            li[i+1][1] = r
        else:
            li[i][1] = r
            r +=1
    else:
        k = li[i][0]
        r = 1
        li[i][1] = r
        r +=1

li.pop()

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

for i in range(m):
    print("{:06d}".format(li[i][0])+"{:06d}".format(li[i][1]))

Solution (Python):
from collections import deque
n,m = map(int,input().split())
prefs = [{} for _ in range(n)]
cities = deque()
for i in range(m):
    p, y = map(int,input().split())
    prefs[p-1][y] = -1
    cities.append((p,y))

for p in prefs:
    years = list(p.keys())
    years.sort()
    for y in range(len(years)):
        p[years[y]] = y+1


for _ in range(m):
    p, y = cities.popleft()
    cid = prefs[p-1][y] + p * 1000000
    print("{:0=12}".format(cid))

Solution (Python):
import sys
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *PY = map(int, read().split())
    city = [(p, y, i) for i, (p, y) in enumerate(zip(*[iter(PY)] * 2))]

    city.sort(key=itemgetter(1))

    counter = [0] * (N + 1)
    ans = [0] * M
    for p, y, i in city:
        counter[p] += 1
        ans[i] = f"{p:>06}{counter[p]:>06}"

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

    return


if __name__ == '__main__':
    main()

Solution (Python):
def digit6(n):
  return ("000000" + str(n))[-6:]

def main():
  N, M = list(map(lambda n: int(n), input().split(" ")))
  CITY = []
  for i in range(M):
    tmp = input().split(" ")
    CITY.append({
      "pref": int(tmp[0]),
      "year": int(tmp[1]),
      "no": i + 1
    })
    
  CITY.sort(key=lambda c: (c["pref"], c["year"]))
  
  order = 0
  pref = ""
  for c in CITY:
    if pref != c["pref"]:
      pref = c["pref"]
      order = 1
    else:
      order += 1
    c["id"] = digit6(pref) + digit6(order)
  
  CITY.sort(key=lambda c: c["no"])
  for i in range(len(CITY)):
    print(CITY[i]["id"])
      
    
  
main()

Solution (Python):
from bisect import bisect_left
n,m = map(int, input().split())
py = []
l = [[] for _ in range(n+1)]
for _ in range(m):
  p,y = map(int, input().split())
  l[p].append(y)
  py.append((p,y))
  
for i in l: i.sort()

for p,y in py:
  s = str(p)
  t = str(bisect_left(l[p],y)+1)
  ans = "0"*(6-len(s))+s + "0"*(6-len(t))+t
  print(ans)

Solution (Python):
from bisect import bisect_left
n,m = map(int, input().split())
py = []
l = [[] for _ in range(n+1)]
for _ in range(m):
  p,y = map(int, input().split())
  l[p].append(y)
  py.append((p,y))
  
for i in l: i.sort()

for p,y in py:
  s = str(p)
  t = str(bisect_left(l[p],y)+1)
  ans = "0"*(6-len(s))+s + "0"*(6-len(t))+t
  print(ans)

Solution (Python):
import math

n, m = map(int, input().split(" "))
pyL = sorted([[i] + list(map(int,
                             input().split(" "))) for i in range(m)],
             key=lambda x: x[2])

li = [1] * (n + 1)

for i in range(len(pyL)):
    index, p, y = pyL[i]
    pyL[i].append(str(p).zfill(6) + str(li[p]).zfill(6))
    li[p] += 1

for py in sorted(pyL, key=lambda x: x[0]):
    print(py[3])

Solution (Python):
n,m = map(int,input().split())
a = []
for i in range(m):
    x,y = map(int,input().split())
    a.append([x,y])
b = a.copy()
c = sorted(b, key=lambda x:(x[0],x[1]))
d = [{}for i in range(10**5+1)]
count = 1
s = '%d' % c[0][0]
s = s.zfill(6)
s2 = '%d' % count
s2 = s2.zfill(6)

d1 = {c[0][1]:s+s2}
for i in range(1,m):
    if c[i][0] == c[i-1][0]:
        count +=1
        s2 = '%d' % count
        s2 = s2.zfill(6)
        d1[c[i][1]] = s+s2
    else:
        d[c[i-1][0]] = d1
        count = 1
        s = '%d' % c[i][0]
        s = s.zfill(6)
        s2 = '%d' % count
        s2 = s2.zfill(6)
        d1 = {c[i][1]:s+s2}
d[c[-1][0]] = (d1)
for i in range(m):
    d2 = d[a[i][0]]
    print(d2.get(a[i][1]))

Solution (Python):
n,m=map(int,input().split())
d=[0]*m
K=[[] for i in range(n)]
for i in range(m):
  p,y=map(int,input().split())
  K[p-1].append((i,y))
for i in range(n):
  K[i].sort(key=lambda x: x[1])
  c=1
  for a,b in K[i]:
    ken=str(i+1)
    t=str(c)
    d[a]=str('0'*(6-len(ken)))+ken+str('0'*(6-len(t)))+t
    c+=1
for i in d:
  print(i)

Solution (Python):
N, M = map(int, input().split())
YP = [[] for _ in range(M)]
for i in range(M):
    p, y = map(int, input().split())
    YP[i] = [y, p, i]
    
YP = sorted(YP)

Num = [0 for _ in range(N+1)]
ID = []


for yp in YP:
    y = yp[0]
    p = yp[1]
    i = yp[2]
    
    Num[p] += 1
    id_p = str(p).zfill(6)
    id_c = str(Num[p]).zfill(6)
    ID.append([i, id_p + id_c])
ID = sorted(ID)
for id in ID:
    print(id[1])

Solution (Python):
n,m=map(int,input().strip().split(" "))
ans=[0]*m
from collections import defaultdict
d=defaultdict(int)
prev=0
d1=defaultdict(int)
ar=[]

def g(i):
    return i[1]
for i in range(m):
    p,y=map(int,input().strip().split(" "))
    ar.append((p,y,i))

ar.sort(key=g)

for i in range(m):
    b=ar[i][0]
    a=i+1
    s=d[b]+1
    d[b]+=1
    a1=str(1000000+b)[1:]
    a2=str(1000000+s)[1:]
    ans[ar[i][2]]=a1+a2
for i in ans:
    print(i)

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

for i in range(m):
    a = list(map(int, input().split()))+[i]
    city.append(a)
city.sort(key=lambda x: x[1])

count = [1 for _ in range(n)]
for k in range(m):
    city[k].append(count[city[k][0]-1])
    count[city[k][0]-1] += 1
city.sort(key=lambda x: x[2])

for i in city:
    print(str(i[0]).zfill(6)+str(i[-1]).zfill(6))

Solution (Python):
n,m = map(int,input().split())
py = [[i+1]+list(map(int,input().split())) for i in range(m)]
pysort = sorted(py,key=lambda x:(x[1],x[2]))

j = 1
cnt = 0
for i in range(m):
    while True:
        if pysort[i][1] == j:
            cnt += 1
            
            pysort[i] += [str(pysort[i][1]).zfill(6)+str(cnt).zfill(6)]
            break
        else:
            cnt = 0
            j += 1

pysortsort = sorted(pysort,key=lambda x:x[0])
[print(a[3]) for a in pysortsort]

Solution (Python):

n,m = map(int, input().split())
pyl = [ [] for _ in range(n+1) ]

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

ans = ['']*m
for p, yil in enumerate(pyl):
    top = str(p).zfill(6)
    yil.sort()
    for order,(y,i) in enumerate(yil):
        bottom = order+1
        bottom = str(bottom).zfill(6)
        ans[i] = top+bottom

for a in ans:
    print(a)

Solution (Python):
N,M=map(int,input().split())
A=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  A[a-1].append((b,i))
ans=[0]*M
for i in range(N):
  d=sorted(A[i])
  n=len(d)
  for j in range(n):
    a,b=d[j]
    D=str(i+1)
    E=str(j+1)
    r=D.zfill(6)+E.zfill(6)
    ans[b]=r
for i in ans:
  print(i)

Solution (Python):
N,M=map(int,input().split())
A=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  A[a-1].append((b,i))
ans=[0]*M
for i in range(N):
  d=sorted(A[i])
  n=len(d)
  for j in range(n):
    a,b=d[j]
    D=str(i+1)
    E=str(j+1)
    r=D.zfill(6)+E.zfill(6)
    ans[b]=r
for i in ans:
  print(i)

Solution (Python):
n,m = map(int,input().split())
ls = [[] for _ in range(n+1)]
di = []
for i in range(m):
    a,b = map(int,input().split())
    ls[a].append([b,i+1])
for j in range(n+1):
    if ls[j] != []:
        ls[j].sort(key=lambda x :x[0])
        for k in range(len(ls[j])):
            di.append([ls[j][k][1],str(10**12+j*10**6+k+1)[1:]])
di.sort(key=lambda x :x[0])
for l in range(m):
    print(di[l][1])

Solution (Python):
n,m=map(int,input().split())
ken=[1 for i in range(n+1)]
inf=[[] for i in range(m)]
def f(x):
    m=0
    while x>0:
        m+=1
        x=x//10
    return m

for i in range(m):
    p,y=map(int,input().split())
    inf[i].append(i+1)
    inf[i].append(p)
    inf[i].append(y)
inf=sorted(inf, key=lambda x: x[2])

for i in range(m):
    inf[i].append(ken[inf[i][1]])
    ken[inf[i][1]]+=1
inf=sorted(inf)


for i in range(m):
    ans=""
    p=inf[i][1]
    y=inf[i][3]
    for j in range(6-f(p)):
        ans+="0"
    ans=ans+str(p)
    
    for j in range(6-f(y)):
        ans=ans+"0"
    ans=ans+str(y)
    print(ans)

Solution (Python):
n,m=map(int,input().split())
ken=[1 for i in range(n+1)]
inf=[[] for i in range(m)]
def f(x):
    m=0
    while x>0:
        m+=1
        x=x//10
    return m

for i in range(m):
    p,y=map(int,input().split())
    inf[i].append(i+1)
    inf[i].append(p)
    inf[i].append(y)
inf=sorted(inf, key=lambda x: x[2])

for i in range(m):
    inf[i].append(ken[inf[i][1]])
    ken[inf[i][1]]+=1
inf=sorted(inf)


for i in range(m):
    ans=""
    p=inf[i][1]
    y=inf[i][3]
    for j in range(6-f(p)):
        ans+="0"
    ans=ans+str(p)
    
    for j in range(6-f(y)):
        ans=ans+"0"
    ans=ans+str(y)
    print(ans)

Solution (Python):
n, m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(m)]
pref = [[] for _ in range(n+1)]

ans = []

for i, c in enumerate(city):
    pref[c[0]].append([i, c[1]])

for i in range(n):
    pref[i + 1].sort(key=lambda x: x[1])
    for j in range(len(pref[i + 1])):
        ans.append([pref[i+1][j][0], str(i+1).zfill(6) + str(j+1).zfill(6)])

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

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

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

S={}
T=[0]*(N+1)
F=[0]*M
for i in range(M):
    P,Y=map(int,input().split())
    F[i]=(P,Y)
    S[(P,Y)]=i
    T[P]+=1

U=[0]*(N+1)
X=[[0]*T[i] for i in range(N+1)]

for P,Y in F:
    X[P][U[P]]=Y
    U[P]+=1

H=[""]*M

for i in range(N+1):
    X[i].sort()

    for j in range(T[i]):
        g=S[(i,X[i][j])]
        H[g]=str(i).zfill(6)+str(j+1).zfill(6)
        j+=1
print("\n".join(H))

Solution (Python):
import sys
from collections import deque


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, m = nm()
    Y = [deque() for _ in range(n)]
    Y_id = []
    order = []
    for i in range(m):
        p, y = nm()
        Y[p - 1].append(y)
        order.append(p)

    for y in Y:
        d = {}
        for i, y_s in enumerate(sorted(y)):
            d[y_s] = i + 1
        Y_id += [d]

    for o in order:
        print('{:06}'.format(o) +
              '{:06}'.format(Y_id[o - 1][Y[o - 1].popleft()]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

(n, m), *q = [[*map(int, i.split())] for i in sys.stdin]
d = defaultdict(list)
for k, v in q:
    d[k].append(v)
c = defaultdict(dict)
for k, v in d.items():
    for i, j in enumerate(sorted(v)):
        c[k][j] = i + 1
for p, y in q:
    print("{:0>6}{:0>6}".format(p, c[p][y]))

Solution (Python):
from collections import defaultdict
(n, m), *q = [[*map(int, i.split())] for i in open(0)]
d = defaultdict(list)
for k, v in q:
    d[k].append(v)
c = defaultdict(dict)
for k, v in d.items():
    for i, j in enumerate(sorted(v)):
        c[k][j] = i + 1
for p, y in q:
    print("{:0>6}{:0>6}".format(p, c[p][y]))

Solution (Python):

(n, m), *q = [[*map(int, i.split())] for i in open(0)]
s = sorted(q)
d = {}
for k, v in s:
    if k not in d:
        d[k] = []
    d[k].append(v)
c = {}
for k, v in d.items():
    i = 0
    if k not in c:
        c[k] = {}
    while i < len(v):
        i += 1
        c[k][v[~-i]] = str(i)
for p, y in q:
    pn = "00000" + str(p)
    cn = "00000" + c[p][y]
    print(pn[-6:] + cn[-6:])

Solution (Python):
N,M=map(int,input().split())
py=[list(map(int,input().split()))for _ in range(M)]
epy=list(enumerate(py))
P=[[]for _ in range(N+1)]
for x in epy:
    P[x[1][0]].append(x)

i=1
ans=[]
while i<=N:
    L=P[i]
    L.sort(key=lambda x:x[1])
    j=0
    while j<len(L):
        L[j][1][1]=j+1
        ans.append(L[j])
        j+=1
    i+=1
ans.sort()

for e,py in ans:
    p,y=map(str,py)
    p='0'*(6-len(p))+p
    y='0'*(6-len(y))+y
    print(p+y)

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

no = {}
ken = [[] for i in range(N)]
for i in range(M):
    p, y = map(int, input().split())
    no[i] = str(p)+'_'+str(y)
    ken[p-1].append(y)

ans = {}
for i in range(N):
    ken[i].sort()
    for j in range(len(ken[i])):
        ans[str(i+1)+'_'+str(ken[i][j])] = str(i+1).zfill(6) + str(j+1).zfill(6)

for i in range(M):
    print(ans[no[i]])

Solution (Python):
n,m=map(int,input().split())
x=[]
y=[]
for i in range(m):
    a,b=map(int,input().split())
    x.append([a,b,i])
x.sort()
s=1
for i in range(m):
    c=x[i][0]
    a=6-len(str(x[i][0]))
    b=["0"]*a
    for j in range(len(str(x[i][0]))):
        b.append(str(x[i][0])[j])
    x[i][0]="".join(b)
    a=6-len(str(s))
    b=["0"]*a
    for j in range(len(str(s))):
        b.append(str(s)[j])
    x[i].append("".join(b))
    if i<m-1:
        if c==x[i+1][0]:
            s+=1
        else:
            s=1
for i in range(m):
    y.append([x[i][2],x[i][0],x[i][3]])
y.sort()
for i in range(m):
    print(y[i][1]+y[i][2])

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

p_y.sort()


res = [0] * m
order = 0
for i in range(m):
    ken, _, index = p_y[i]
    if ken != p_y[i - 1][0] and i > 0:
        order = 1
    else:
        order += 1
    res[index] = [ken, order]




for i in range(m):
    ken = str(res[i][0]).zfill(6)
    order = str(res[i][1]).zfill(6)
    print(ken + order)

Solution (Python):
import numpy as np

N,M=map(int,input().strip().split())
PY=np.array([list(map(int,input().strip().split())) for _ in range(M)])

l=[[] for n in range(N)]
for m in range(M):
    l[PY[m,0]-1].append(PY[m,1])

dp={}
for n in range(N):
    if l[n]:
        l[n].sort()
        for i in range(len(l[n])):
            city="000000"+str(n+1)
            num="000000"+str(i+1)
            dp[(n,l[n][i]-1)]=str(city[-6:]+num[-6:])
for m in range(M):
    print(dp[(PY[m,0]-1,PY[m,1]-1)])