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):
from collections import defaultdict
import bisect
N,M = map(int, input().split())
dic = defaultdict(list)
cities = []
for _ in range(M):
  p,y = map(int,input().split())
  cities.append([p,y])
for item in sorted(cities):
  dic[item[0]].append(item[1])
for item in cities:
  print("%06d%06d"%(item[0],bisect.bisect(dic[item[0]],item[1])))

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])
cnt = [0] * (n + 1)

sorted_py = sorted(py, key = lambda x: (x[1], x[2]))
for i in range(m):
    cnt[sorted_py[i][1]] += 1
    city_id = str(sorted_py[i][1]).zfill(6)+str(cnt[sorted_py[i][1]]).zfill(6)
    sorted_py[i].append(city_id)

sorted_py = sorted(sorted_py, key = lambda x: x[0])
for i in range(m):
    print(sorted_py[i][3])

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
prefecture = [[] for _ in range(n+1)]
tpl_lst=[]
for i in range(m):
    p, y = map(int, input().split())
    prefecture[p].append(y)
    tpl_lst.append((p,y))

for p in prefecture:
    if len(p)>=2:
        p.sort()

d = defaultdict(list)
for idx, pre in enumerate(prefecture):
    if len(pre)>=1:
        for i, year in enumerate(pre):
            d[(idx, year)]=[idx, i+1]

for tpl in tpl_lst:
    id = d[tpl][0]*(10**6) + d[tpl][1]
    id = str(id)
    id = "0"*(12-len(id)) + id
    print(id)

Solution (Python):
N,M=map(int,input().split())
l=[]
for i in range(M):P,Y=map(int,input().split());l.append([i,P,Y,0])
from operator import*
l.sort(key=itemgetter(2))
P=[0]*N
for i in range(M):P[l[i][1]-1]+=1;l[i][3]=P[l[i][1]-1]
l.sort(key=itemgetter(0))
for i in range(M):print(str(l[i][1]).zfill(6)+str(l[i][3]).zfill(6))

Solution (Python):
if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = []
    for i in range(1, M+1):
        p, y = map(int, input().split())
        PY.append((y, p, i))
    PY.sort()
    ANS = [""]*(M+1)
    P = [0]*(N+1)
    for y, p, i in PY:
        P[p] += 1
        ANS[i] = "{0:06d}".format(p) + "{0:06d}".format(P[p])
    
    for ans in ANS:
        if ans=="": continue
        print(ans)

Solution (Python):
N, M = map(int, input().split())
A = []
B = [[] for i in range(N)]
for i in range(M):
  P, Y = map(int, input().split())
  A.append([P, Y])
  B[P-1].append(Y)
for i in range(N):
  B[i].sort()
d = {}
for i in range(N):
  for y in range(len(B[i])):
    d[(i+1, B[i][y])] = y + 1
for i in range(M):
  print('{:0=6}'.format(A[i][0]) + '{:0=6}'.format(d[(A[i][0], A[i][1])]))

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

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

    inlis = sorted(inlis, key = lambda x:x[2])
    anslis = []
    tmpdic = dict()

    for i in range(m):
        j, p, y = inlis[i][0], inlis[i][1], inlis[i][2]
        
        if p not in tmpdic:
            tmpdic[p] = 1
        else:
            tmpdic[p] += 1
        
        num = str(tmpdic[p]).zfill(6)
        ken = str(p).zfill(6)

        ans = ken + num
        anslis.append([j,ans])
    
    anslis = sorted(anslis, key = lambda x:x[0])

    for [city, num] in anslis:
        print(num)


    



if __name__ == "__main__":
    main()

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

P = []
Y = []
I = []
for i in range(m):
    a, b = map(int, input().split())
    P.append(a)
    Y.append(b)
    I.append(i)

Z = zip(P, Y, I)
Z = sorted(Z)
P, Y, I = zip(*Z)

N = []
c = P[0]
d = 1
for i in range(m):
    if c == P[i]:
        N.append("{0:06d}{1:06d}".format(c, d))
        d += 1
    else:
        c = P[i]
        d = 1
        N.append("{0:06d}{1:06d}".format(c, d))
        d += 1

Z = zip(I, N)
Z = sorted(Z)
I, N = zip(*Z)
for i in N:
    print(i)

Solution (Python):
import bisect
n,m = map(int,input().split())
x = [list() for i in range(n)]
p = []
y = []
for i in range(m):
  s,t = map(int,input().split())
  p.append(s)
  y.append(t)
  x[s-1].append(t)
for i in range(n):
  x[i].sort()
  
for i in range(m):
  index = bisect.bisect_left(x[p[i]-1],y[i])
  print("{:06}{:06}".format(p[i],index+1))

Solution (Python):
import bisect

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

ans=[]

re=[[] for _ in range(n)]



for _ in range(m):
  a=list(map(int,input().split()))
  re[a[0]-1].append(a[1])
  ans.append(a)
  
d=[]
for f in re:
  sor=[]
  
  new=sorted(list(set(f)))
  
  for i in f:
    c=bisect.bisect_left(new,i)
    sor.append(c+1)
    
  d.append(sor)
    
  
for x in ans:
  p=x[0]
  q=d[p-1].pop(0)
  print(str('{:0=6}'.format(p))+str('{:0=6}'.format(q)))

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

ans=[""]*M
A=sorted(A, key=lambda x: x[1])
A=sorted(A,key=lambda x:x[0])

now=A[0][0]
cnt=1
for i in range(M):
    pref=str(A[i][0])
    
    if A[i][0]!=now:
        cnt=1
    year=str(cnt)
    now=A[i][0]
    cnt+=1

    ans[A[i][2]]=pref.zfill(6)+year.zfill(6)

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

Solution (Python):








def solve(N, M, PY):
    ken = [0] * (N + 1)
    PY = [PY[i] + [i] for i in range(M)]
    PY.sort(key=lambda x: x[1])
    for i in range(M):
        p, y, s = PY[i]
        ken[p] += 1
        PY[i].append(ken[p])
    PY.sort(key=lambda x: x[2])
    for p, y, s, n in PY:
        print(('000000' + str(p))[-6:] + ('000000' + str(n))[-6:])


if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = [[int(i) for i in input().split()] for _ in range(M)]
    solve(N, M, PY)

Solution (Python):
N,M=map(int,input().split())
PY=[[list(map(int,input().split())),i] for i in range(M)]
PY.sort()
cnt=[0 for i in range(N+1)]
ans=[]
for i in range(M):
    cnt[PY[i][0][0]]+=1
    ans.append([PY[i][1],str(PY[i][0][0]).zfill(6)+str(cnt[PY[i][0][0]]).zfill(6)])
ans.sort()
for i in range(M):
    print(ans[i][1])

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

ans=[]

re=[[] for _ in range(n)]



for _ in range(m):
  a=list(map(int,input().split()))
  re[a[0]-1].append(a[1])
  ans.append(a)
  
d={}
for f in re:
  new=sorted(f)
  
  for i in range(len(new)):
    d[new[i]]=i+1
  
for x in ans:
  p=x[0]
  q=d[x[1]]
  print(str('{:0=6}'.format(p))+str('{:0=6}'.format(q)))

Solution (Python):
N,M = map(int,input().split())
py = [list(map(int,input().split()))+[i] for i in range(M)]
py.sort()
P = py[0][0]
c = 0
ans = []
for p,y,i in py:
    if p == P:
        c += 1
    else:
        P = p
        c = 1
    ansc = str(c)
    ansp = str(p)
    anser = "0" * (6-len(ansp)) + ansp + "0" *(6-len(ansc)) + ansc
    ans.append([i,anser])
ans.sort()
for i,anser in ans:
    print(anser)

Solution (Python):
n,m = map(int,input().split())
l = [[] for i in range(m)]
for i in range(m):
    a,b = map(int,input().split())
    l[i] = [a,b,i]
l = list(sorted(l,key=lambda x: (x[0], x[1])))
ans = [[] for i in range(m)]
x = 0
y = 1
for i in range(m):
    if x != l[i][0]:
        x = l[i][0]
        y = 1
    else:
        y += 1
    a = str(x).zfill(6)
    b = str(y).zfill(6)
    ans[i] = [a+b,l[i][2]]
ans = list(sorted(ans,key=lambda x: x[1]))
for i in range(m):
    print(ans[i][0])

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

Solution (Python):
def main():
    
    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 x: (x[1], x[2]))

    num = 1
    for i in range(0, m):
        if i == 0:
            py[i].append(num)
        else:
            if py[i][1] == py[i-1][1]:
                num += 1
            else:
                num = 1
            py[i].append(num)

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

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


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[1])
ans = []
cnt = [0] * N
for p, y, i in PY:
  ans.append(("{0:06d}".format(p)+"{0:06d}".format(cnt[p-1]+1), i))
  cnt[p-1] += 1
ans.sort(key=lambda x:x[1])
for a in ans:
  print(a[0])

Solution (Python):
from bisect import bisect_right
n, m = map(int, input().split())
py = [tuple(map(int, input().split())) for _ in range(m)]
d = dict()
for p, y in py:
    if p not in d.keys():
        d[p] = [y]
    else:
        d[p].append(y)

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

for p, y in py:
    print(str(p).zfill(6) + str(bisect_right(d[p], y)).zfill(6))

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

py.sort()
anslst=[""]*m
dic=defaultdict(int)

for i in range(m):
    p,y,index=py[i]
    dic[p]+=1
    pnum=str(p)
    pnum="0"*(6-len(pnum))+pnum
    ynum=str(dic[p])
    ynum="0"*(6-len(ynum))+ynum
    anslst[index]=pnum+ynum
for i in range(m):
    print(anslst[i])

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

C = []
for i in range(M):
    p, y = map(int, input().split())
    C.append([i, p, y])
C.sort(key=lambda x: (x[1], x[2]))

ans = []
k = C[0][1]
n = 1
for i in range(M):
    city = C[i][1]
    if k != city:
        k = city
        n = 1
    number = f'{city:06}{n:06}'
    ans.append([C[i][0], number])
    n += 1
ans.sort(key=lambda x: x[0])
for i in range(M):
    print(ans[i][1])

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

C = []
for i in range(M):
    p, y = map(int, input().split())
    C.append([i, p, y])
C.sort(key=lambda x: (x[1], x[2]))

ans = []
k = C[0][1]
n = 1
for i in range(M):
    city = C[i][1]
    if k != city:
        k = city
        n = 1
    number = f'{city:06}{n:06}'
    ans.append([C[i][0], number])
    n += 1
ans.sort(key=lambda x: x[0])
for i in range(M):
    print(ans[i][1])

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n,m = i_map()
    l = []
    for i in range(m):
        p,y = i_map()
        l.append([i,p,y,0])

    l.sort(key = lambda x :(x[1], x[2]))
    ken = l[0][1]
    cnt = 1

    for i in l:
        if i[1] == ken:
            i[3] = cnt
            cnt += 1
        else:
            i[3] = 1
            cnt = 2
            ken = i[1]
    l.sort(key = lambda x:x[0])

    ans = []
    for i in l:
        ans.append(str(i[1]).zfill(6) + str(i[3]).zfill(6))
    for i in ans:
        print(i)

if __name__=="__main__":
    main()

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n, m= LI()
    dic = collections.defaultdict(list)
    ans_lst = []

    for i in range(m):
        p, y = LI()
        dic[p].append((i, y))

    for key in dic.keys():
        dic[key].sort(key=lambda x: x[1])
        pfil = str(key).zfill(6)

        for i in range(len(dic[key])):
            id = pfil + str(i+1).zfill(6)
            ans_lst.append((dic[key][i][0], id))

    ans_lst.sort()
    ans = list(zip(*ans_lst))[1]
    print(*ans,sep="\n")
main()

Solution (Python):

"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""




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

dic = dict()
dic2 = dict()
P = list()


for i in range(M):
    p, y = map(int,input().split())
    
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
    P.append((p,y))




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

for key in dic.keys():
    for i in range(len(dic[key])):
        dic2[dic[key][i]] = i+1

for i in range(M):
    p, y = P[i]
    ans = str(p).zfill(6)+str(dic2[y]).zfill(6)
    """
    
    ans = ''
    ans += '0'*( 6 - len(str(p))) + str(p)
    
    t = dic2[y]
    ans += '0'*( 6 - len(str(t))) + str(t)
    """
    print(ans)

Solution (Python):

"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""




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

dic = dict()
dic2 = dict()
P = list()


for i in range(M):
    p, y = map(int,input().split())
    
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
    P.append((p,y))




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

for key in dic.keys():
    for i in range(len(dic[key])):
        dic2[dic[key][i]] = i+1

for i in range(M):
    p, y = P[i]
    
    
    ans = ''
    ans += '0'*( 6 - len(str(p))) + str(p)
    
    t = dic2[y]
    ans += '0'*( 6 - len(str(t))) + str(t)
    print(ans)

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


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


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

for i in range(N):
    biggest = len(keep[i])
    j = 0
    while j < biggest:
        keep[i][j][2] = j + 1
        j += 1
    keep2 += keep[i]

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

for i in range(M):
    ans = ''
    ans += '0' * (6 - len(str(keep2[i][1]))) + str(keep2[i][1])
    ans += '0' * (6 - len(str(keep2[i][2]))) + str(keep2[i][2])
    print(ans)

Solution (Python):
import bisect

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

x=[list(map(int,input().split())) for i in range(m)]

lst=[[] for i in range(n)]

for i,v in x:
    lst[i-1].append(v)

for i in range(n):
    lst[i].sort()

for i,v in x:
    z=bisect.bisect_left(lst[i-1],v)+1

    print('0'*(6-len(str(i)))+str(i)+'0'*(6-len(str(z)))+str(z))

Solution (Python):
import bisect

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

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

P_1 = [sorted(l) for l in P]

for p,y in Q:
    a = str(p).zfill(6)
    b = str(bisect.bisect(P_1[p-1], y)).zfill(6)
    print(a+b)

Solution (Python):
from sys import stdin
input = stdin.buffer.readline

def main():
    n, m = map(int, input().split())

    yp = [(0, 0)] * m
    for i in range(m):
        p, y = map(int, input().split())
        yp[i] = (y, p-1, i)

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

    ans = [('', '')] * m
    cnt = [1] * n
    for y, p, i in yp:
        ans[i] = (str(p+1), str(cnt[p]))
        cnt[p] += 1

    for i, j in ans:
        print('0' * (6 - len(i)) + i + '0' * (6 - len(j)) + j)

main()

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

sortPY = sorted(PY, key=lambda x: x[1])
prefec = [0]*(N+1)
res = []
for p, y, i in sortPY:
    prefec[p] += 1
    strp = str(p)
    ID = '0'*(6-len(strp)) + strp + '0'*(6-len(str(prefec[p]))) + str(prefec[p])
    res.append([ID, i])

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

Solution (Python):
N,M=map(int,input().split())
d={}
PY=[]
import bisect
for _ in range(M):
    p,y=map(int,input().split())
    PY.append((p,y))
    t=d.get(p, [0])
    i=bisect.bisect_left(t,y)
    t.insert(i,y)
    d[p]=t
    
dx={}
for k, v in d.items():
    for i in range(len(v)):
        dx[(k,v[i])]=i
        
for p,y in PY:
    print(str(p).zfill(6)+str(dx[(p,y)]).zfill(6))

Solution (Python):

url = "https://atcoder.jp//contests/abc113/tasks/abc113_c"

def main():
    t = list(map(int, input().split()))
    town = {k: [] for k in range(1, t[0]+1)}
    all_town = []
    for _ in range(t[1]):
        tmp = list(map(int, input().split()))
        all_town.append(tmp)
        town[tmp[0]].append(tmp[1])
    ans = {}
    for k in town:
        town[k].sort()
        tmp_dic = {town[k][i]: str(k).zfill(6)+str(i+1).zfill(6) for i in range(len(town[k]))}
        ans.update(tmp_dic)
    for at in all_town:
        print(ans[at[1]])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

def f(x):
    return '0'*(6-div10(x))+str(x)

N,M=mint()
S=dict()
for i in range(M):
    p,y=mint()
    S.setdefault(p,[])
    S[p].append((y,i))
ans=[0]*M
for p in S:
    S[p].sort()
    for j in range(len(S[p])):
        y,i=S[p][j]
        ans[i]=f(p)+f(j+1)
lprint(ans)

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

ids=["" for i in range(m)]
for i in range(n):
  l[i].sort()
  for j in range(len(l[i])):
    ids[l[i][j][1]]="{:0>6d}".format(i+1)+"{:0>6d}".format(j+1)
print("\n".join(ids))

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

p_dict = {}

for i in range(M):
  p, y = map(int, input().split())
  if p not in p_dict.keys():
    p_dict[p] = [[y, p, i]]
  else:
    p_dict[p].append([y, p, i])
  
ans = []
for p in p_dict.keys():
  p_dict[p].sort()
  for i in range(len(p_dict[p])):
    p_dict[p][i].append(i + 1)
    ans.append(p_dict[p][i])
    
ans.sort(key=lambda x: x[2])
for y, p, oi, si in ans:
  print("{:06d}{:06d}".format(p, si))

Solution (Python):
import bisect
n,m = map(int,input().split())
x = [list() for i in range(n)]
p = []
y = []
for i in range(m):
  s,t = map(int,input().split())
  p.append(s)
  y.append(t)
  x[s-1].append(t)
for i in range(n):
  x[i].sort()
  
for i in range(m):
  index = bisect.bisect_left(x[p[i]-1],y[i])
  print("{:06}{:06}".format(p[i],index+1))

Solution (Python):
import bisect
n,m = map(int,input().split())
x = [list() for i in range(n)]
p = []
y = []
for i in range(m):
  s,t = map(int,input().split())
  p.append(s)
  y.append(t)
  x[s-1].append(t)
for i in range(n):
  x[i].sort()
  
for i in range(m):
  index = bisect.bisect_left(x[p[i]-1],y[i])
  print("{:06}{:06}".format(p[i],index+1))

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

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

answers = {}

for i in range(n):
    number = numbers[i]
    if len(number) == 0:
        continue
    new_number = sorted(number.items(), key = lambda x : x[1]) 
    cnt = 1
    for num in new_number:
        answers[num[0]] = (6-len(str(i+1)))*'0' + str(i+1) + (6-len(str(cnt)))*'0' + str(cnt)
        cnt += 1

answer = sorted(answers.items(), key = lambda x : x[0])

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

Solution (Python):
N,M=map(int,input().split())
numbers=[{} for n in range(N)]
for m in range(M):
    P,Y=map(int,input().split())
    numbers[P-1][m]=Y
answers={}
for n in range(N):
    number=numbers[n]
    if len(number)==0:
        continue
    new_number=sorted(number.items(), key=lambda x:x[1])
    suuji=1
    for num in new_number:
        answers[num[0]]=(6-len(str(n+1)))*'0'+str(n+1)+(6-len(str(suuji)))*'0'+str(suuji)
        suuji+=1
answer=sorted(answers.items(), key=lambda x:x[0])
for ans in answer:
    print(ans[1])

Solution (Python):
def make_code(prifacture_num, city_num):
    s1 = str(prifacture_num)
    while len(s1) != 6:
        s1 = '0' + s1
    s2 = str(city_num)
    while len(s2) != 6:
        s2 = '0' + s2
    return s1 + s2


prifacture_cnt, city_cnt = map(int, input().split())
data = [list(map(int, input().split())) for i in range(city_cnt)]
city_data = []

for i in range(city_cnt):
    city_data.append([data[i][0], data[i][1], i])

city_data.sort()
city_code = []
prifacture = city_data[0][0]
cnt = 0
for city in city_data:
    if prifacture == city[0]:
        cnt+=1
        s = make_code(prifacture, cnt)
        city_code.append([city[2], s])
    else:
        cnt = 1
        prifacture = city[0]
        s = make_code(prifacture, cnt)
        city_code.append([city[2], s])

city_code.sort()
for num,code in city_code:
    print(code)

Solution (Python):
class Info:
  def __init__(self, num, p, y, id):
    self.num = num
    self.p = p
    self.y = y
    self.id = id
    
n, m = map(int, input().split())
info = [Info(0, 0, 0, '')]
for num in range(1, m + 1):
  p, y = map(int, input().split())
  info.append(Info(num, p, y, ''))

info = sorted(info, key=lambda x: (x.p, x.y))

cnt = 1
for i in range(1, m + 1):
  if info[i].p != info[i-1].p:
    cnt = 1
  else:
    cnt += 1
  info[i].id = "{0:06d}{1:06d}".format(info[i].p, cnt)

info = sorted(info, key=lambda x: x.num)
info.pop(0)

for x in info:
  print(x.id)

Solution (Python):
import bisect

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

N, M = cin()
l1 = [[] for i in range(N + 1)]
l2 = []
for i in range(M):
    in1, in2 = cin()
    l1[in1].append(in2)
    l2.append([in1, in2])

for i in range(N + 1):  l1[i] = sorted(l1[i])
    
for i in range(M):
    c = l2[i]
    n = bisect.bisect_left(l1[c[0]], c[1]) + 1
    ans = str(c[0]).zfill(6) + str(n).zfill(6)
    print(ans)

Solution (Python):

from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)





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




def I(): return int(sys.stdin.buffer.readline())





def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()




def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')







def IR(n): return [I() for i in range(n)]







def LIR(n): return [LI() for i in range(n)]







def SR(n): return [S() for i in range(n)]







def LSR(n): return [LS() for i in range(n)]







def SRL(n): return [list(S()) for i in range(n)]


def main():
    n, m = LI()
    
    lst = [[] for i in range(n)]
    ans = [0 for i in range(m)]

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

    for i in range(n):
        if len(lst[i]) > 1:
            lst[i].sort()
        for j, pair in enumerate(lst[i]):
            ans[pair[1]] = str(i+1).zfill(6) + str(j + 1).zfill(6)

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


if __name__ == "__main__":
    main()

Solution (Python):
class City:
    def __init__(self, prefecture, year):
        self.prefecture = prefecture
        self.year = year
        self.order = None

    def __eq__(self, other):
        if self.year == other.year:
            return True
        return False

    def __le__(self, other):
        if self.year <= other.year:
            return True
        return False

    def __lt__(self, other):
        if self.year < other.year:
            return True
        return False

    def __ge__(self, other):
        if self.year >= other.year:
            return True
        return False

    def __gt__(self, other):
        if self.year > other.year:
            return True
        return False


cities = []
n,m=[int(i) for i in input().split()]
prefecture=[[] for i in range(n+1)]



for i in range(m):
    p,y=[int(j) for j in input().split()]
    new_city=City(p, y)
    cities.append(new_city)
    prefecture[p].append(new_city)

for pref_list in prefecture:
    pref_list.sort()
    for i ,pref in enumerate(pref_list):
        pref.order=i+1

for city in cities:
    print(str(city.prefecture).zfill(6)+str(city.order).zfill(6))

Solution (Python):


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

P=[[] for _ in [0]*(N+1)]

for i in range(M):
    p,y=map(int,input().split())
    P[p].append((y,i))
    
from bisect import bisect_left as bl

res=[]
for p in range(N+1):
    Y=P[p][:]
    if not Y:
        continue
    
    sortY=sorted(list(set(Y)))
        
    zatY=[]
    for t_y in Y:
        zatY.append(bl(sortY,t_y))
    
    for index in zatY:
        y,i=sortY[index]
        num=10**12+p*10**6+index+1
        res.append((str(num)[1:],i))

res=[y for y,i in sorted(res,key=lambda x:x[1])]
print(*res,sep='\n')

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

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

sorted_cities = sorted(cities, key=lambda x: (x[0], x[1]))
cnt = 1
ans = []
for i in range(m-1):
    p_id = str(sorted_cities[i][0]).rjust(6, '0')
    c_id = str(cnt).rjust(6, '0')
    ans.append([sorted_cities[i][2], p_id+c_id])
    if sorted_cities[i][0] != sorted_cities[i+1][0]:
        cnt = 1
    else:
        cnt += 1

p_id = str(sorted_cities[m-1][0]).rjust(6, '0')
c_id = str(cnt).rjust(6, '0')
ans.append([sorted_cities[m-1][2], p_id+c_id])
ans.sort()

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

Solution (Python):


import sys

from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, m = input_int_list()
    cnt = defaultdict(int)
    cities = []
    ids = [None] * m
    for i in range(0, m):
        p, y = input_int_list()
        cities.append((i, p, y))

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

    for i, p, y in cities:
        num = cnt[p] + 1
        cnt[p] += 1
        _id = "{:0=6}{:0=6}".format(p, num)
        ids[i] = _id

    for _id in ids:
        print(_id)

    return


if __name__ == "__main__":
    main()

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_sorted = sorted(p_y)
li_id = []
prev_p = -1
cnt = 1

for i in p_y_sorted:
    if(prev_p != i[0]):
        prev_p = i[0]
        cnt = 1
    id = str(i[0]).zfill(6) + str(cnt).zfill(6)
    li_id.append([i[2], id])
    cnt += 1

li_id_sorted = sorted(li_id)

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

Solution (Python):
n,m=map(int,input().split())
c=[[] for _ in range(n)]
for i in range(m):
    p,y=map(int,input().split())
    c[p-1].append([i,y])
ans=[0]*m
for i in range(n):
    c[i].sort(key=lambda x:x[1])
    for j in range(len(c[i])):
        ID=str(i+1).zfill(6)+str(j+1).zfill(6)
        ans[c[i][j][0]]=ID
print(*ans,sep="\n")

Solution (Python):
N,M=map(int,input().split())
PY=[list(map(int,input().split())) for i in range(M)]
PYI=sorted([(p,y,i) for i,(p,y) in enumerate(PY)])
r=['']*M
a,b=0,0
for p,y,i in PYI:
    if a!=p:
        a,b=p,1
    else:
        b+=1
    r[i]=str(p).zfill(6)+str(b).zfill(6)
print(*r,sep='\n')

Solution (Python):
N, M = map(int, input().split())
li = [0] * M

for i in range(M):
    P, Y = map(int, input().split())
    li[i] = (P, Y)

li2 = sorted(li)

s = '000000'
tmp = 0
cnt = 1
dic = {}
for i in li2:
    if tmp == i[0]:
        cnt += 1
    else:
        cnt = 1
        tmp = i[0]

    s1 = s[0:6-len(str(i[0]))] + str(i[0])
    s2 = s[0:6-len(str(cnt))] + str(cnt)
    s3 = s1 + s2
    dic[i] = s3

for i in li:
    print(dic[i])