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 _ in range(m)]
c=[0]*-~n
id={}
for p,y in sorted(a,key=lambda x:x[1]):
    c[p]+=1
    id[y]=format(p,"06")+format(c[p],"06")
for _,y in a:
    print(id[y])

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
PY = [tuple(map(int, input().split())) for _ in range(m)]
sorted_PY = sorted(PY)
cnt = 1
now = sorted_PY[0][0]
d = defaultdict(int)
for p, y in sorted_PY:
    if now != p:
        cnt = 1
        now = p
    d[y] = (p, cnt)
    cnt += 1

for p, y in PY:
    l, r = map(str, d[y])
    l = '0'*(6-len(l)) + l
    r = '0'*(6-len(r)) + r
    print(l+r)

Solution (Python):
import bisect

n, m = map(int, input().split())
li = []
d = {}
for _ in range(m):
    p, y = map(int, input().split())
    li.append([p, y])
    if p not in d:     
        d[p] = [y]
    else:
        d[p].append(y)
for k, v in d.items():
    v.sort()
for p, y in li:
    r = bisect.bisect_right(d[p], y)
    print(str(p).zfill(6) + str(r).zfill(6))

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

from operator import itemgetter
PY= sorted(PY,key=itemgetter(1),reverse = False)
PY = sorted(PY,key=itemgetter(0),reverse = False)

B= []
pre = 0
city = 0
for i in range(M):
    if pre != PY[i][0]:
        pre =  PY[i][0]
        city = 1
        B.append([str(pre).rjust(6, '0') + str(city).rjust(6, '0') ,PY[i][2]])
    else:
        city += 1
        B.append([str(pre).rjust(6, '0') + str(city).rjust(6, '0') ,PY[i][2]])

B= sorted(B,key=itemgetter(1),reverse = False)        
for i in range(M):
    print(B[i][0])

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
PY = [tuple(map(int, input().split())) for _ in range(m)]
sorted_PY = sorted(PY)
cnt = 1
now = sorted_PY[0][0]
d = defaultdict(int)
for p, y in sorted_PY:
    if now != p:
        cnt = 1
        now = p
    d[y] = (p, cnt)
    cnt += 1

for p, y in PY:
    l, r = map(str, d[y])
    if len(l) < 6:
        light = '0'*(6-len(l)) + str(l)
    else:
        light = str(l)
    if len(r) < 6:
        right = '0'*(6-len(r)) + str(r)
    else:
        right = str(r)
    print(light+right)

Solution (Python):
import bisect
n,m=map(int,input().split())
k=[[] for _ in range(n)]
p=[0 for _ in range(m)]
y=[0 for _ in range(m)]
for i in range(m):
	a,b = map(int,input().split())
	y[i] = b
	p[i] = a
	k[a-1].append(b)
for i in range(n):
	k[i].sort()
ansl = []
for i in range(m):
	d1 = str(p[i]).zfill(6)
	d2 = str(bisect.bisect_right(k[p[i]-1], y[i])).zfill(6)
	ansl.append(d1+d2)
print("\n".join(ansl))

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

for p,j in d.items():
    j.sort(key=lambda x:x[1])
    for i in range(len(j)):
        a[j[i][0]-1]=format(p,'0>6')+format(i+1,'0>6')
print(*a,sep='\n')

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


def read():
    N, M = map(int, input().strip().split())
    IPY = []
    for i in range(M):
        p, y = map(int, input().strip().split())
        IPY.append((i, p, y))
    return N, M, IPY


def solve(N, M, IPY):
    X = [1 for i in range(N+1)]
    IPY.sort(key=lambda ipy: ipy[2])
    zipcode = []
    for i, p, y in IPY:
        zipcode.append((i, p, X[p]))
        X[p] += 1
    zipcode.sort()
    for i, p, x in zipcode:
        print("{:06d}{:06d}".format(p, x))


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter  
from collections import defaultdict
def main():
    n, m = map(int, readline().split())
    cities = []
    for i in range(m):
        p, y = map(int, readline().split())
        cities.append((i+1, p, y))
    cities.sort(key=itemgetter(2))
    dd = defaultdict(int)
    ansdd = defaultdict(str)
    for i in range(m):
        cid, p, y = cities[i]
        dd[p] += 1
        x = dd[p]
        ansdd[cid] = '{:0=6}'.format(p)+'{:0=6}'.format(x)
    for i in range(1, m+1):
        print(ansdd[i])
if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left
n, m = map(int, input().split())
city_list = [[0] for _ in range(n + 1)]
city = [[]]
for _ in range(m):
    p, y = map(int, input().split())
    city_list[p].append(y)
    city.append([p, y])
for i in range(1, n + 1):
    city_list[i].sort()
for i in range(1, m + 1):
    ID = ''
    p = city[i][0]
    order = str(bisect_left(city_list[p], city[i][1]))
    p = str(p)
    ID = ID + ('0' * (6 - len(p)))
    ID += p
    ID += ('0' * (6 - len(order)))
    ID += order
    print(ID)

Solution (Python):
from bisect import bisect_left
n, m = map(int, input().split())
city_list = [[0] for _ in range(n + 1)]
city = [[]]
for _ in range(m):
    p, y = map(int, input().split())
    city_list[p].append(y)
    city.append([p, y])
for i in range(1, n + 1):
    city_list[i].sort()
for i in range(1, m + 1):
    ID = ''
    p = city[i][0]
    order = str(bisect_left(city_list[p], city[i][1]))
    
    p = str(p)
    ID = ID + ('0' * (6 - len(p)))
    ID += p
    ID += ('0' * (6 - len(order)))
    ID += order
    print(ID)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18


def compress(A):
    return {element: i+1 for i, element in enumerate(sorted(set(A)))}

n, m = Is()
PY = TIR(m)
A = [list() for _ in range(n+1)]
for p, y in PY:
    A[p].append(y)
B = [compress(a) for a in A]

for p, y in PY:
    ans = str(p).zfill(6) + str(B[p][y]).zfill(6)
    print(ans)

Solution (Python):
if __name__ == "__main__":
    N, M = map(int, input().split())
    T = []
    for i in range(M):
        p, y = map(int, input().split())
        T.append((p, y, i))
    T.sort()
    ID = []
    cp = -1
    count = -1
    for p, y, i in T:
        if p != cp:
            cp = p
            count = 1
        ID.append((i, "0"*(6-len(str(cp)))+str(cp)+"0"*(6-len(str(count)))+str(count)))
        count += 1
    ID.sort()
    for i , id in ID:
        print(id)

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):
N, M = map(int, input().split())
cnt = [1 for _ in range(N)] 
l = []

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

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

for i in range(M):
    p = l[i][0] 
    x = str(cnt[p-1]) 
    cnt[p-1] += 1

    str_p = str(p)
    while len(str_p) != 6:
        str_p = "0" + str_p

    while len(x) != 6:
        x = "0" + x
    
    l[i][0] = str_p
    l[i][1] = x

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

for i, j, _ in l:
    print(i+j)

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

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

for i in range(1, n + 1):
    tmp = d[i]
    tmp.sort(key=lambda x: x[1])
    for i, j in enumerate(tmp):
        j.append(i + 1)

ans = []
for a, b in d.items():
    for i in b:
        i.append(a)
        ans.append(i)

for _, _, c, p in sorted(ans):
    print("{:06}{:06}".format(p, c))

Solution (Python):
from collections import defaultdict
d = defaultdict(list)


def sortpy(y):
    return {x: i for i, x in enumerate(sorted(y), 1)}


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

for p, y in py:
    d[p].append(y)

nd = {p: sortpy(y) for p, y in d.items()}

for p, y in py:
    print('{:06g}{:06g}'.format(p, nd[p][y]))

Solution (Python):
n, m = list(map(int, input().split()))
yp = []
for i in range(m):
  y, p = list(map(int, input().split()))
  yp.append([i+1, y, p])
  
yp.sort(key=lambda x: x[2])
counter = [1]*n
for i in range(m):
  num1 = "0"*(6-len(str(yp[i][1]))) + str(yp[i][1])
  junban = str(counter[yp[i][1]-1])
  counter[yp[i][1]-1] += 1
  num2 = "0"*(6-len(junban)) + junban
  yp[i].append(num1+num2)
  
yp.sort(key=lambda x: x[0])
for i in range(m):
  print(yp[i][3])

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

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


v=[[] for i in range(n+1)]

ans=[0 for i in range(m)]

for i in range(m):
    v[x[i][0]].append(x[i])

for i in range(n+1):
    v[i].sort()

for i in range(n+1):
    for j in range(len(v[i])):
        
        l=str(0)*(6-len(str(i)))+str(i)
        ans[v[i][j][2]]=l+str(0)*(6-len(str(j+1)))+str(j+1)

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

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

P = []
Y = []

d = {}
ans = [0] * M
for i in range(1,N+1):
    d[i] = []

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

for k in d.keys():
    d[k] = sorted(d[k], key=lambda x: x[1])
    for i in range(len(d[k])):
        ans[d[k][i][0]] = '{}{}'.format(str(k).zfill(6),str(i+1).zfill(6))

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

Solution (Python):
n, m = map(int, input().split())
cnt = [[] for _ in range(n + 1)]
for i in range(m):
    p, y = map(int, input().split())
    cnt[p].append((y, i))
buf = [None] * m
for p, l in enumerate(cnt):
    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):
n,m = map(int,input().split())
cnt = [[] for i in range(n+1)]

for i  in range(m):
    p,y = map(int,input().split())
    cnt[p].append((y,i))
buf = [None] * m
for p,l in enumerate(cnt):
    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))

"""
n, m = map(int, input().split())
cnt = [[] for _ in range(n + 1)]
for i in range(m):
    p, y = map(int, input().split())
    cnt[p].append((y, i))
buf = [None] * m
for p, l in enumerate(cnt):
    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):
N, M = map(int, input().split())

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

y = {}
for i in range(N):
    x[i].sort()
    for j, Y in enumerate(x[i]):
        y[(i+1, Y)] = j + 1
for i in range(M):
    print('{}{}'.format(str(a[i][0]).zfill(6), str(y[a[i]]).zfill(6)))

Solution (Python):
def mips():
  return map(int,input().split())
def rev(data):
    a = data[0]
    data[0] = data[1]
    data[1] = a
    return None
N,M = mips()
data = dict()
for i in range(M):
    pref,year = mips()
    if pref not in data:
        data[pref] = [[year,i+1,pref]]
    else:
        data[pref].append([year,i+1,pref])
ans = []
for pref in data:
    data[pref].sort()
    for i in range(len(data[pref])):
        data[pref][i][0] = i+1
        rev(data[pref][i])
        ans.append(data[pref][i])
ans.sort()
for i in range(M):
    ken = str(ans[i][2])
    when = str(ans[i][1])
    ken,when = format(ken,'0>6'),format(when,'0>6')
    print(ken+when)

Solution (Python):

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



citydic={}

def make_id(p):
    dif=6-len(str(p))
    res="".join(["0" for i in range(dif)])
    return res+str(p)

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


id_dic={}

for pref, val in citydic.items():
    l=sorted(val,key=lambda x: x[2])
    for x,temp in enumerate(l,1):
        i,p,y=temp
        
        cityid=make_id(p)+make_id(x)
        id_dic[i]=cityid

for i in range(1,m+1):
    print(id_dic[i])

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

new_pyn=sorted(pyn)

cnt=1
i=1
j=0


while(j<m):
    if new_pyn[j][0] == i:
        new_pyn[j].append(cnt)
        cnt+=1
        j+=1

    else:
        cnt=1
        i+=1
final=sorted(new_pyn,key=lambda x:x[2])


for i in range(m):
    a=str(final[i][0])
    b=str(final[i][3])
    print(str(a.zfill(6))+str(b.zfill(6)))

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

d={}
for i in range(m):
    p,y=map(int, input().split())
    if p not in d:
        d[p]=[[y,p,i]]
    else:
        d[p].append([y,p,i])

bango_list=['0']*m
for key in d:
    d[key].sort()
    for i in range(len(d[key])):
        p_bango=str(key).zfill(6)
        x_bango=str(i+1).zfill(6)
        bango_list[d[key][i][2]]=p_bango+x_bango

for b in bango_list:
    print(b)

Solution (Python):
from sys import stdin, setrecursionlimit
from bisect import bisect_left


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    py = [list(map(int, input().split())) for _ in range(m)]

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

    for p, y in py:
        summary[p - 1].append(y)

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

    for p, y in py:
        print(str(p).zfill(6), str(bisect_left(summary[p - 1], y) + 1).zfill(6), sep='')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
py = []
lst = [[] for _ in range(n)]
for _ in range(m):
    tmp = list(map(int, input().split()))
    py.append((tmp[0], tmp[1]))
    lst[tmp[0] - 1].append(tmp[1])
dic = {}
for i, l in enumerate(lst):
    l.sort()
    for j, num in enumerate(l):
        dic[(i + 1, num)] = "{:06}".format(i + 1) + "{:06}".format(j + 1)
for l in py:
    print(dic[l])

Solution (Python):

import sys
input = sys.stdin.readline









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


A = [[] for _ in range(N+1)]
for i in range(M):
    p,y = PY[i]
    A[p].append((y,i))

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

Ans = [0]*M
for i in range(1,N+1):
    for j in range(len(A[i])):
        y,k = A[i][j]
        Ans[k] = "{:06d}{:06d}".format(i,j+1)

for ans in Ans:
    print(ans)

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

Solution (Python):

import sys
import bisect

"""
ABC113_C ID 学び：
 python の0埋め　s.rjust(digit,0) でいける
 sortを県ごとにしないといけない、とわかれば、input, sort , outputの３段かいに別れる
どんな配列を持てばいいかは事前に考える。
実際にそこまで立てて、inputをローカルでやると良い
"""

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, m = map(int, input().split())
lis_p = [[] for _ in range(n)]  
city = [[0, 0] for _ in range(m)]  
idx_p = []  

for i in range(m):
    p, y = map(int, input().split())
    city[i][0] = p - 1
    city[i][1] = y
    lis_p[p - 1].append(y)
for pref in range(n):
    k = len(lis_p[pref])
    
    idx = []
    if k > 0:
        lis_p[pref], idx = zip(*sorted(zip(lis_p[pref], range(k))))
    idx_p.append(list(idx))

for i in range(m):
    
    print(str(city[i][0] + 1).rjust(6, "0"), end="")
    print(str(1 + bisect.bisect_left(lis_p[city[i][0]], city[i][1])).rjust(6, "0"))

Solution (Python):
from operator import itemgetter

def id(n):
    if len(str(n)) >= 6:
        return str(n)
    return "0"*(6-len(str(n)))+str(n)

n,m = map(int,input().split())
data = [[] for i in range(n+1)]
for i in range(m):
    p,y = map(int,input().split())
    data[p].append((i,y))
ans = []
for i in range(n+1):
    if data[i]:
        data[i].sort(key=itemgetter(1))
        for j in range(len(data[i])):
            ans.append((data[i][j][0],id(i)+id(j+1)))
ans.sort()
for i,j in ans:
    print(j)

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

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

y = {}
for i in range(N):
    x[i].sort()
    for j, Y in enumerate(x[i]):
        y[(i+1, Y)] = j + 1
for i in range(M):
    print('{}{}'.format(str(a[i][0]).zfill(6), str(y[a[i]]).zfill(6)))

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

x = {}

for i in range(len(PY)):
    prefecture = PY[i][0]
    year = PY[i][1]

    if prefecture in x.keys():
        x[prefecture].append((year, i))
    else:
        x[prefecture] = [(year, i)]

for i in x:
    x[i] = sorted(x[i])



for i in x:
    for t in range(len(x[i])):
        PY[x[i][t][1]] = str(i).zfill(6) + str(t + 1).zfill(6)

for py in PY:
    print(py)

Solution (Python):
from collections import defaultdict

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

ids = {}
nums = defaultdict(int)
for i, p, y in IPY:
    nums[p] += 1
    ids[i] = '{:06d}{:06d}'.format(p, nums[p])
for i in range(1, M + 1):
    print(ids[i])

Solution (Python):
from operator import itemgetter
n,m=map(int,input().split())
a=[]
for i in range(m):
    pi,yi=map(int,input().split())
    a.append([i,pi,yi])
b=[]
c=[]
for i in range(n):
    b.append([])
    c.append([])
for i in range(m):
    x=a[i][0]
    y=a[i][2]
    b[a[i][1]-1].append([x,y])

for i in range(n):
    b[i].sort(key=itemgetter(1))
    l=len(b[i])
    for j in range(l):
        a[b[i][j][0]].append(j+1)
for i in range(m):
    xi=a[i][1]
    yi=a[i][3]
    print('{0:06d}{1:06d}'.format(xi,yi))

Solution (Python):
N, M = map(int, input().split())
py = []
for i in range(M):
    p, y = map(int, input().split())
    py += [[i, p, y]]
py = sorted(py, key=lambda x:(x[1], x[2]))
cnt = 0
pre = py[0][1]
ans = []
for n, p, y in py:
    if pre != p:
        cnt = 1
        pre = p
    else:
        cnt += 1
        
    ans += [[n, str(p).zfill(6)+str(cnt).zfill(6)]]

ans = sorted(ans, key=lambda x:x[0])
for _, n in ans:
    print(n)

Solution (Python):
n,m=map(int,input().split())
citydic={}
for i in range(m):
    p,y=map(int,input().split())
    add=[i,p,y]
    temp=citydic.get(p,[])
    temp.append(add)
    citydic[p]=temp


def make_id(p):
    dif=6-len(str(p))
    res="".join(["0" for i in range(dif)])
    return res+str(p)

ansdic={}
for key, v in citydic.items():
    l=sorted(v,key=lambda x: x[2])
    
    for x, templ in enumerate(l,1):
        
        citynum,p,y=templ
        id1=make_id(p)+make_id(x)
        ansdic[citynum]=id1

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

Solution (Python):
n,m=map(int,input().split())
citydic={}
for i in range(m):
    p,y=map(int,input().split())
    add=[i,p,y]
    temp=citydic.get(p,[])
    temp.append(add)
    citydic[p]=temp


def make_id(p):
    dif=6-len(str(p))
    res="".join(["0" for i in range(dif)])
    return res+str(p)

ansdic={}
for key, v in citydic.items():
    l=sorted(v,key=lambda x: x[2])
    
    for x, templ in enumerate(l,1):
        
        citynum,p,y=templ
        id1=make_id(p)+make_id(x)
        ansdic[citynum]=id1

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

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

ans = [None]*M
for p, iys in enumerate(piys):
    iys.sort()
    for k, (y, i) in enumerate(iys):
        ans[i] = "%06d%06d" % (p+1, k+1)

for i in ans:
    print(i)

Solution (Python):
import bisect
n,m = map(int,input().split())
data = []
for i in range(m):
    data.append(list(map(int,input().split())))
r = sorted(data,key= lambda x:(x[0],x[1]))
o = [[] for _ in range(100001)]

for i in range(m):
    o[r[i][0]].append(r[i][1])

for i in range(m):
    print("0"*(6-len(str(data[i][0]))),end="")
    print(data[i][0],end="")
    num = bisect.bisect_left(o[data[i][0]],data[i][1])+1
    print("0"*(6-len(str(num))),end="")
    print(num)

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

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

for i in range(N):
    li[i].sort()

for p,y in zip(P,Y):
    zenhan="0"*(6-len(str(p)))+str(p)
    x=bisect.bisect_left(li[p-1], y)+1
    kouhan="0"*(6-len(str(x)))+str(x)
    print(zenhan+kouhan)

Solution (Python):
n,m=map(int,input().split())
num=[]
ans=[""]*m
numcount=[1]*n
count=1
for i in range(m):
    p,y=map(int,input().split())
    num.append([p,y,i])
stry= lambda val: val[1]
num.sort(key=stry)
for i in range(m):
    p=str(num[i][0])
    y=str(numcount[int(num[i][0])-1])
    numcount[int(num[i][0])-1]+=1
    ans[num[i][2]]="0"*(6-len(p))+p+"0"*(6-len(y))+y
for i in range(m):
    print(ans[i])

Solution (Python):
n,m = map(int,input().split())
l = []
s = ""
tmp = 1
for i in range(m):
  p,y = map(int,input().split())
  l.append([str(p).zfill(6),y,i+1])
  
l = sorted(l, key=lambda x:(x[0],x[1]))

for i in range(m):
  s = ""
  if i == 0 or l[i-1][0] != l[i][0]:
    tmp = 1
  else:
    tmp += 1
  s = l[i][0] + str(tmp).zfill(6)
  l[i].append(s)
    
l = sorted(l, key=lambda x:(x[2]))

for i in range(m):
  print(l[i][3])

Solution (Python):

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

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

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


d = defaultdict(int)
ress = []
for py in PYs:
    i, p, y = py
    ress.append((i, p, d[p]+1))
    d[p] += 1

ress.sort(key=lambda x: x[0])
for res in ress:
    i, p, o = res
    print(str(p).zfill(6)+str(o).zfill(6))

Solution (Python):
import bisect
from collections import defaultdict

N, M = map(int, input().split(' '))
cities = []
years = defaultdict(list)
for _ in range(M):
    p, y = map(int, input().split(' '))
    cities.append((p, y))
    years[p].append(y)

for p in years.keys():
    years[p].sort()

for p, y in cities:
    print('{:06}{:06}'.format(p, bisect.bisect_right(years[p], y)))

Solution (Python):
from collections import Counter

N, M = map(int, input().split(' '))
records = [tuple(map(int, input().split(' '))) for _ in range(M)]
s_records = sorted(records)

counter = Counter()
d = {}

for p, y in s_records:
    counter[p] += 1
    d[(p, y)] = '{:06}{:06}'.format(p, counter[p])

for p, y in records:
    print(d[(p, y)])

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

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

ans = [None]*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(*ans, sep = '\n')

Solution (Python):
import sys
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
city = {}
yton = {}
for i in range(m):
    p,y = map(int, sys.stdin.readline().rstrip("\n").split())
    if p not in city.keys():
        city[p] = []
        city[p].append(y)
        yton[y] = i
    else:
        city[p].append(y)
        yton[y] = i
ans = [None]*m
for p in city.keys():
    city[p].sort()
    for i,y in enumerate(city[p]):
        ans[yton[y]] = str(p*(10**6)+i+1).zfill(12)
print(*ans, sep = '\n')

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

l=[[] for j in range(n)]
for i in range(m):
  p,y=map(int,input().split())
  l[p-1].append([y,i])
for j in range(n):
  l[j].sort(key=lambda x:x[0])
lis=[]
for j in range(n):
  for t in range(len(l[j])):
    pre='0'*(6-len(str(j+1)))+str(j+1)
    y='0'*(6-len(str(t+1)))+str(t+1)
    b=pre+y
    lis.append([b,l[j][t][1]])
lis.sort(key=lambda x:x[1])
for li in lis:
  print(li[0])

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

ans=[0]*m
for i in range(n):
    sa=sorted(a[i],key=lambda x:x[0])
    order=1
    for tpl in sa:
        ans[tpl[1]]='0'*(6-len(str(i+1)))+str(i+1)+'0'*(6-len(str(order)))+str(order)
        order+=1
print(*ans,sep='\n')

Solution (Python):
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    pref = defaultdict(list)
    pref_list = [0] * (M + 1)
    for i in range(M):
        p, y = map(int, input().split())
        pref_list[i + 1] = p
        pref[p].append((y, i + 1))
    
    for p in pref: pref[p].sort()
    order = [0] * (M + 1)
    for p in pref:
        for x, (y, i) in enumerate(pref[p]):
            order[i] = x + 1
    
    for i in range(1, M + 1):
        p = pref_list[i]
        x = order[i]
        print("{p:06}{x:06}".format(p=p, x=x))





if __name__ == "__main__":
    main()

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

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

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


ken = 0 
for i in range(m):
    if pyi[i][0] != ken: 
        ken = pyi[i][0] 
        x = 1 
    else: 
        x += 1 
    pyi[i].append(x) 

pyi.sort(key=lambda x: x[2]) 
for i in range(m): 
    print(str(pyi[i][0]).zfill(6)+str(pyi[i][3]).zfill(6))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
    n, m = map(int, input().split())
    h = {}
    pres = [1] * n
    cities = []
    year_pres = {}
    years = []
    for i in range(m):
        p, y = map(int, input().split())
        cities.append((p, y))
        year_pres[y] = p
        years.append(y)
    years.sort()
    for year in years:
        pre = year_pres[year]
        h[year] = pres[pre - 1]
        pres[pre - 1] += 1
    for city in cities:
        a = str(city[0]).zfill(6)
        b = str(h[city[1]]).zfill(6)
        print(a + b)

if __name__ == '__main__':
    main()

Solution (Python):
def resolve():
    n,m=map(int,input().split())
    py=[[0]*3 for _ in range(m)]
    for i in range(m):
        p,y=map(int,input().split())
        py[i][0],py[i][1],py[i][2]=p,y,i
    py.sort()
    ans=[[''] for _ in range(m)]
    cnt=[0]*(n+1)
    for p,y,i in py:
        cnt[p]+=1
        ans[i]='0'*(6-len(str(p)))+str(p)+'0'*(6-len(str(cnt[p])))+str(cnt[p])
    for i in ans:
        print(i)


if __name__ == '__main__':
    resolve()

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

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

c = []
for x, p in enumerate(pre):
    p.sort(key = lambda x : x[1])

    for j, (i, y) in enumerate(p):
        c.append((i, x+1, j+1))

c.sort(key = lambda x :x[0])
for _, x, y in c:
    print(str(x).zfill(6)+str(y).zfill(6))

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


prefs = [[] for _ in range(n + 1)]


cities = []

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

for i in range(1, n + 1):
    prefs[i].sort()

table = {}

for i in range(1, n + 1):
    for j in range(len(prefs[i])):
        year, city = prefs[i][j]
        pref = i
        table[(pref, city)] = j + 1

for i in range(m):
    city = i + 1
    pref = cities[i]
    order = table[(pref, city)]

    pref = str(pref)
    order = str(order)
    ans = format(pref, '0>6') + format(order, '0>6')
    print(ans)

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

rank_map={}
rank=0
p=None

for t in sorted(data):
    if p!=t[0]:
        p=t[0]
        rank=1
    rank_map[t]='%06d%06d' % (t[0], rank)
    rank+=1

for t in data:
    print(rank_map[t])

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


data = [tuple(map(int, input().split())) for _ in range(m)]





m={}
n=0
p=None
for t in sorted(data):

    if p!=t[0]:
        p=t[0]
        n=1
    m[t]='%06d%06d' % (t[0], n)
    n+=1

for k in data:
    print(m[k])

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

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

ID=[0 for _ in range(M)]
for j in range(N):
    Pre[j].sort()
    for k in range(len(Pre[j])):
        ID[Pre[j][k][1]-1]=str(j+1).zfill(6)+str(k+1).zfill(6)

for d in ID:
    print(d)