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 sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

ans = [0] * M
for i in range(1, N + 1):
    if P[i] == 0:
        continue
    upper = ('0' * 5 + str(i))[-6:]
    A = sorted(P[i])
    for i, (_, j) in enumerate(A):
        lower = ('0' * 5 + str(i + 1))[-6:]
        ans[j] = upper + lower
        
for a in ans:
    print(a)

Solution (Python):
import bisect

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

for P,Y in PY:
    bisect.insort_left(L[P-1],Y)

for P,Y in PY:
    P_ans = str(P).zfill(6)
    Y_ans = str(bisect.bisect_right(L[P-1],Y)).zfill(6)
    print(P_ans,Y_ans,sep="")

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

Pref = sorted(Pref, key=lambda x: x[2])
Pref = sorted(Pref, key=lambda x: x[1])
c = 0
P = Pref[i][1]
for i in range(m):
    if P != Pref[i][1]:
        c = 1
        P = Pref[i][1]
    else:
        c += 1
    Pref[i][3] = str(Pref[i][1]).zfill(6) + str(c).zfill(6)

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

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

def main():
    N, M = map(int, input().split())
    PY = [tuple([i] + list(map(int, input().split()))) for i in range(M)]
    result = []
    p_city = defaultdict(int)
    for py in sorted(PY, key = lambda x: x[2]):
        p_city[py[1]] += 1
        code = str(py[1]).zfill(6) + str(p_city[py[1]]).zfill(6)
        result.append((py[0], code))
    print("\n".join([r[1] for r in sorted(result, key = lambda x: x[0])]))


if __name__ == '__main__':
    main()

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

pref = []
for i in range(M):
    pp, yy = map(int, input().split())
    pref.append((yy, pp, i))

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

count = [0]*(N+1)
names = ['']*(M+1)
for i in range(M):
    yy, pp, id = pref[i]
    count[pp] += 1
    names[id] = '{:06d}{:06d}'.format(pp, count[pp])

for id in range(M):
    print(names[id])

Solution (Python):
import bisect

n, m = [int(i) for i in input().split()]

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

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

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


for i in range(m):
    a = str(p[i]).zfill(6)
    b = str(bisect.bisect(vals[p[i]-1], y[i])).zfill(6)
    print(a+b)

Solution (Python):

import collections
n,m = map(int, raw_input().split())
cities = [map(int,raw_input().split(' ')) + [i] for i in range(m)]
cities.sort(key  = lambda x :x[1] )
h = {}
def fill(s):
	return (max(0,6 - len(str(s))) * '0') + str(s)

cc = collections.Counter()
for p,y,i in cities:
	cc[p] += 1
	h[i] = '{}{}'.format(fill(p),fill(cc[p]))

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

Solution (Python):
n, m = map(int, input().split())
p, y = zip(*[map(int, input().split()) for _ in range(m)])

city_data = {}
for i in range(m):
    city_data[i] = [p[i], y[i], None]

cities = list(city_data.keys())
cities.sort(key=lambda city: city_data[city])

pref = None
for city in cities:
    if city_data[city][0] == pref:
        yidx += 1
    else:
        yidx = 1
        pref = city_data[city][0]
    city_data[city][2] = '{:06d}{:06d}'.format(pref, yidx)

for i in range(m):
    print(city_data[i][2])

Solution (Python):
def readinput():
    n,m=list(map(int,input().split()))
    prefs=[]
    for _ in range(n+1):
        prefs.append([])
    for i in range(1,m+1):
        pi,yi=list(map(int,input().split()))
        prefs[pi].append([i,yi])
    return n,m,prefs

def main(n,m,prefs):
    citycodes=['000000000000']*(m+1)
    for i in range(1,n+1):
        pref=prefs[i]
        pref.sort(key=lambda x:x[1])
        prefcode='{:06}'.format(i)
        
        for j, city in enumerate(pref):
            citycode='{:06}'.format(j+1)
            
            citycodes[city[0]]=prefcode+citycode
    return citycodes

if __name__=='__main__':
    n,m,prefs=readinput()
    citycodes=main(n,m,prefs)
    for i in range(1,m+1):
        print(citycodes[i])

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

Solution (Python):
import bisect
def zaatu(a):
    b=list(set(a))
    for i in range(len(a)):
        a[i]=bisect.bisect_left(b,a[i])
    return a
n,m=map(int,input().split())
a=[[] for _ in range(n)]
b=[]
for i in range(m):
    p,y=map(int,input().split())
    a[p-1].append([p,y,i])
for i in range(n):
    a[i].sort(key=lambda x:x[1])
for i in range(n):
    for j in range(len(a[i])):
        b.append([a[i][j],j+1])
b.sort(key=lambda x:x[0][2])
for i in b:
    print('0'*(6-len(str(i[0][0])))+str(i[0][0])+'0'*(6-len(str(i[1])))+str(i[1]))

Solution (Python):
N, M = map(int, input().split())
data = [list(map(int, input().split())) + [_] for _ in range(M)]
data = sorted(data, key=lambda x: (x[0], x[1]))

order = 1
for i in range(M):
    if not i == 0 and not data[i][0] == data[i-1][0]:
        order = 1
    data[i].append(str(data[i][0]).zfill(6) + str(order).zfill(6))
    order += 1

data = sorted(data, key=lambda x: (x[2]))
for x in data:
    print(x[3])

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

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

submit =[0]*M
for i in range(M):
    D[lst[i][0]-1].append((lst[i][1],i))



for i,d in enumerate(D):
    
    d.sort(key=lambda x: x[0])
    
    for k,(y,j) in enumerate(d):
        
        submit[j] = str(i+1).zfill(6)+str(k+1).zfill(6)

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

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, i)]
    else:
        d[p].append((y, i))

ans = [0]*m
for k, v in d.items():
    vl = v
    vl.sort()
    num = 1
    for city in vl:
        pre = str(k).zfill(6)
        c = str(num).zfill(6)
        ans[city[1]] = pre+c
        num += 1
print(*ans,sep="\n")

Solution (Python):
n, m = map(int, input().split())
def zs(num):
    k = 6 - len(str(num))
    return '0' * k + str(num)
lst = []
for i in range(m):
  lst.append(tuple(map(int, input().split())))
slst = sorted(lst)
dic = {}
temp = 0
for i in range(m):
  if slst[i][0] == slst[i - 1][0]:
    temp += 1
  else:
    temp = 1
  dic[slst[i]] = zs(slst[i][0]) + zs(temp)
for i in lst:
  print(dic[i])

Solution (Python):
def get_(i):
    zero_len = 6-len(str(i))
    return '0'*zero_len+str(i)

def get_idx(n,L):
    if len(L)<100:
        left=0
        right=len(L)
    else:    
        left=0
        right=len(L)

        i=0
        while i < 50:
            half=int((left+right)/2)
            if n <= L[half]:
                right = half
            else:
                left = half
            i+=1
        
    if left >= 1:
        left -= 1
        
    for i in range(left,right+1):
        if L[i]==n:
            return i

N,M = list(map(int,input().split()))
N_list=[[] for n in range(N)]
M_list=[]

for m in range(M):
    P,Y=list(map(int,input().split()))
    N_list[P-1].append(Y)
    M_list.append([P,Y])
    
for n in N_list:
    n.sort()
    
for m in M_list:
    p=get_(m[0])
    
    i=get_idx(m[1],N_list[m[0]-1])+1
    i=get_(i)
    
    print(p+i)

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

ans = [[0,0]]*(M)

prefectures = [[] for i in range(0,N+1,1)]
for i in range(M):
    prefectures[PY[i][0]].append([PY[i][1],i])
for i in range(N+1):
    prefectures[i].sort()
for i in range(N+1):
    for j in range(len(prefectures[i])):
        ans[prefectures[i][j][1]]=[i,j+1]

for i in range(M):
    ans[i][0] = str(ans[i][0]).zfill(6)
    ans[i][1] = str(ans[i][1]).zfill(6)
    print("".join(ans[i]))

Solution (Python):
from bisect import bisect_left

def solve():
    N,M = map(int, input().split())
    cities_in_prefecture = [[] for _ in range(N)]
    city_ids = []
    PYs = []
    for _ in range(M):
        P,Y = map(int, input().split())
        PYs.append((P,Y))
        cities_in_prefecture[P-1].append(Y)
    for p in range(N): cities_in_prefecture[p].sort()
    for P, Y in PYs:
        x = bisect_left(cities_in_prefecture[P-1], Y)
        
        print('{0:06d}{1:06d}'.format(P, x+1), flush=True)
        
solve()

Solution (Python):
def c_name(a, b):
    x = '0'*(6-len(str(a)))
    y = '0'*(6-len(str(b)))
    return x + str(a) + y + str(b)

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

C = []

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

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

d = {}
tmp = C[0][1]
num = 0
for i in C:
    if i[1] == tmp:
        num += 1
        d[i[0]] = c_name(i[1],num)
    else:
        tmp = i[1]
        num = 1
        d[i[0]] = c_name(i[1],num)

ans = sorted(d.items())

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

Solution (Python):
def tashi(n):
  c=str(n)
  return "0"*(6-len(c))+c
R=list()
N,M=map(int,input().split())
for i in range(M):
  P,Y=map(int,input().split())
  R.append([P,Y,i])
R=sorted(R)
f=1
k=0
for i in range(M):
  c=R[i]
  if c[0]==f:
    k+=1
    c.append(k)
  else:
    k=1
    c.append(k)
  f=c[0]
K=[0]*M
for i in range(M):
  c=R[i]
  K[c[2]]=tashi(c[0])+tashi(c[3])
for i in range(M):
  print(K[i])

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
order = []
dd = defaultdict(int)

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


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

res = defaultdict(str)
for i, pp, yy in order:
    dd[pp] += 1
    res[i] = str(pp).zfill(6) + str(dd[pp]).zfill(6)

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

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

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

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

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

for i in range(n):
    for j in range(len(lst[i])):
        lst[i][j].append(j+1)

lst=[i for j in lst for i in j]
lst=sorted(lst,key=lambda x:x[0])

for i in range(m):
    left=str(lst[i][1])
    right=str(lst[i][3])
    prnt=["0"*(6-len(left)),left,"0"*(6-len(right)),right]
    print("".join(prnt))

Solution (Python):
import sys

from collections import deque, Counter, defaultdict



import math
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n, m = rl()
lis=[[] for _ in range(n+1)]
shi=[tuple(rl()) for _ in range(m)]
ans=dict()

for i in shi:
    lis[i[0]].append(i[1])

for i, com in enumerate(lis):
    if len(com)==0:continue

    for j,num in enumerate(sorted(com)):
        ans[num]="0"*(6-len(str(i)))+ str(i) + "0"*(6-len(str(j+1)))+str(j+1)

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m = map(int, readline().split())
ipy = [[i] + list(map(int, readline().split())) for i in range(m)]

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

c = [0] * n
l = []
for i, p, y in ipy:
    c[p - 1] += 1
    x = str(format(p, '06') + format(c[p - 1], '06'))
    l.append([i, x])

l.sort()
for i, v in l:
    print(v)

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

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


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


ans = ['']*m
for ii, pp, yy in order:
    dd[pp] += 1
    ans[ii] = '{:0>6}{:0>6}'.format(pp, dd[pp])

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

Solution (Python):
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N, M = in_nn()
    t = in_na()
    PY = list(zip(t, t))

    d = defaultdict(list)

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

    ans = dict()
    for k, v in d.items():
        v.sort()
        for i, y in enumerate(v):
            ans[(k, y)] = '{:0>6}{:0>6}'.format(k, i + 1)

    for i in range(M):
        p, y = PY[i]
        print(ans[(p, y)])


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np




(N,M) = map(int, input().split())
PY = []

for i in range(1,M+1):
    (P,Y) = map(int, input().split())
    PY += (i,P,Y),

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

result = {}

order = 1
last = 0
for (i, P, Y) in PY:
    if last != P:
        order = 1
        last = P
    result.update({i:('{:0>6}'.format(P) + '{:0>6}'.format(order))})
    order += 1

for i in range(1,M+1):
    print(result[i])

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], x[1]))

prev_p, i = PY[0][0], PY[0][2]
out = [None] * len(PY)
out[i] = str(prev_p).zfill(6) + str(1).zfill(6)

cnt = 1
for p, y, idx in PY[1:]:
    if p != prev_p:
        cnt = 0

    cnt += 1
    prev_p = p
    out[idx] = str(p).zfill(6) + str(cnt).zfill(6)


for x in out:
    print(x)

Solution (Python):
def nto6str(num):
    s =list('000000')
    numS = str(num)
    L_numS = len(numS)
    for i in range(L_numS):
        s[i*(-1)-1] = numS[i*(-1)-1]
    ans = ''.join(s)
    return ans

N,M =list(map(int,input().split()))
Lis = []
for i in range(M):
    a=list(map(int,input().split()))
    a.append(i)
    Lis.append(a)
b = sorted(Lis)
pref = 0
city = 0
for i in range(M):
    if b[i][0] != pref:
        pref = b[i][0]
        city = 1
    b[i][1] = city
    city +=1
for i in range(M):
    b[i][0] = nto6str(b[i][0])
    b[i][1] = nto6str(b[i][1])
c = sorted(b,key = lambda x:x[2])
for i in range(M):
    print(''.join(c[i][0:2]))

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

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

for a in dic:
    a.sort()

dic2 = [{} for _ in range(N+1)]
for p in range(N+1):
    dic2[p] = {y:i+1 for i,y in enumerate(dic[p])}

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

Solution (Python):
n, m = map(int,input().split())
p = [[i] + list(map(int,input().split())) for i in range(m)]
p = sorted(p, key=lambda x:(x[1], x[2]))
for i in range(m):
    p[i][1] = str(p[i][1]).zfill(6)
    if i >= 1 and p[i][1] == p[i-1][1]:
        p[i][2] = str(int(p[i-1][2])+1).zfill(6)
    else:
        p[i][2] = str(1).zfill(6)
p = sorted(p, key=lambda x:(x[0]))
for i in range(m):
    print(p[i][1]+p[i][2])

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))
    



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

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

Solution (Python):


from collections import defaultdict


def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N, M = MII()

    d = defaultdict(int)

    py = []
    for i in range(M):
        P, Y = MII()
        py.append((i, P, Y))
    py = sorted(py, key=lambda x: x[2])
    

    ans = [''] * M
    for i, j, k in py:
        d[j] += 1
        ans[i] = f'{j:06d}{d[j]:06d}'
    
    print('\n'.join(ans))


if __name__ == '__main__':
    main()

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

A = [[] for _ in range(N+1)]

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

City = []
for i in range(N+1):
    A[i] = sorted(A[i])
    for j, a in enumerate(A[i]):
        pref = i
        city = j+1
        City.append([a[1], str(pref).zfill(6) + str(city).zfill(6)])

City = sorted(City)
for city in City:
    print(city[1])

Solution (Python):

import sys


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    tuple = list(zip(P, Y, [i for i in range(M)]))
    tuple.sort()
    numbers = [0 for _ in range(M)]
    index = 0
    pre = tuple[0][0]
    for t in tuple:
        if pre != t[0]:
            pre = t[0]
            index = 0
        index += 1
        numbers[t[2]] = f"{str(t[0]).zfill(6)}{str(index).zfill(6)}"
    for n in numbers:
        print(n)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    P = [int()] * (M)  
    Y = [int()] * (M)  
    for i in range(M):
        P[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    solve(N, M, P, Y)

if __name__ == '__main__':
    main()

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

ids=[]

import bisect

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

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

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

for info in ids:
    p=info[0]
    y=info[1]
    index = bisect.bisect_left(arr[p-1],y)

    print(str(info[0]).zfill(6)+str(index+1).zfill(6))

Solution (Python):
def solve():
    n, m = map(int, input().split())
    d = [{} for _ in range(n)]
    ans = [0 for _ in range(m)]
    for i in range(m):
        p, y = map(int, input().split())
        d[p-1][i] = y
    for i in range(n):
        d[i] = sorted(d[i].items(), key=lambda x:x[1])
        d[i] = list(map(list, d[i]))
        for x in range(len(d[i])):
            ans[d[i][x][0]] = '{:0=6}'.format(i + 1) + '{:0=6}'.format(x + 1)
    for i in ans:
        print(i)




if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    
    
    
    
    
    

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


    num = 0
    city = 0
    city_str = ""
    numdict = {}

    for i in sorted(py_s, key=lambda x: [x[0], int(x[1])]):
        if city != i[0]:
            city = i[0]
            city_str = format(city, '06')
            num = 0
        num += 1
        numdict[i[1]] = "".join([city_str, format(num, '06')])

    for i in py_s:
        print(numdict[i[1]])



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """2 3
1 32
2 63
1 12"""
        output = """000001000002
000002000001
000001000001"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2 3
2 55
2 77
2 99"""
        output = """000002000001
000002000002
000002000003"""
        self.assertIO(test_input, output)

    
    def test_original1(self):
        test_input = """100000 4
100000 1000000000
2 1
2 10
2 2
"""
        output = """100000000001
000002000001
000002000003
000002000002"""
        self.assertIO(test_input, output)

    
    def t_est_original2(self):
        test_input = """4 1
1 20
"""
        output = """000001000001"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
n,m = map(int,input().split())
all_town = [[] for i in range(n)]
for i in range(m):
  p_y = list(map(int,input().split()))
  p_y.append(i)
  all_town[p_y[0]-1].append(p_y)

i_id = []
for town in all_town:
  town.sort(key=lambda x: x[1])
  for i in range(len(town)):
    left = "{:0=6}".format(town[i][0])
    right = "{:0=6}".format(i+1)
    i_id.append([town[i][2],left+right])
    
i_id.sort(key=lambda x: x[0])
for id in i_id:
  print(id[1])

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

p.sort(key=lambda x:x[2]) 
c = [1]*(n+1)
for i in range(m):
  p[i][2] = c[p[i][1]]
  c[p[i][1]] += 1
p.sort()
for i in range(m):
  print( str(p[i][1]).zfill(6) + str(p[i][2]).zfill(6))

Solution (Python):
from collections import defaultdict

def main():
    d = defaultdict(int)
    n, m = [int(i) for i in input().split()]
    py = {}

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

    res = [''] * m
    for v in sorted(py.items(), key=lambda x:x[1]):
        d[v[1][0]] += 1
        res[v[0]] = str(v[1][0]).zfill(6) + str(d[v[1][0]]).zfill(6)
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

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

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

now=0
p1=items[0][0]
ans=[]
for p,y,ind in items:
    if p==p1:
        now+=1
        tmp=str(p*10**6+now)
        tmp=(12-len(tmp))*"0"+tmp
        ans.append((ind,tmp))
    else:
        now=1
        p1=p
        tmp=str(p*10**6+now)
        tmp=(12-len(tmp))*"0"+tmp
        ans.append((ind,tmp))

ans.sort()
for _ , j in ans:
    print(j)

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

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

now=0
p1=items[0][0]
ans=[]
for p,y,ind in items:
    if p==p1:
        now+=1
        tmp=str(p*10**6+now)
        tmp=(12-len(tmp))*"0"+tmp
        ans.append((ind,tmp))
    else:
        now=1
        p1=p
        tmp=str(p*10**6+now)
        tmp=(12-len(tmp))*"0"+tmp
        ans.append((ind,tmp))

ans.sort()
for _,j in ans:
    print(j)

Solution (Python):



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

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

now=0
p1=items[0][0]
ans=[]
for p,y,ind in items:
    
    if p==p1:
        now+=1
        tmp=str(p*10**6+now)
        tmp=(12-len(tmp))*"0"+tmp
        
        ans.append((ind,tmp))
    else:
        now=1
        p1=p
        tmp=str(p*10**6+now)
        tmp=(12-len(tmp))*"0"+tmp
        ans.append((ind,tmp))
ans.sort()
for _ , j in ans:
    print(j)

Solution (Python):
N, M, *_PY = map(int, open(0).read().split())
PY = []

for i in range(M):
    PY.append([_PY[i*2],_PY[i*2+1], i+1])
    
now_p = 0

for py in sorted(PY):
    if py[0] != now_p:
        now_p = py[0]
        cnt = 1
    else:
        cnt += 1

    py.append(str(py[0]).zfill(6) + str(cnt).zfill(6))
    
for py in PY:
    print(py[3])

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

A,B={},[]
for p,y,num in PY:
    if p not in A:
        A[p]=1
        B.append([p,A[p],num])
    else:
        A[p] +=1
        B.append([p,A[p],num])

for a,b,c in sorted(B,key=lambda x:x[2]):
    print(str(a).zfill(6)+str(b).zfill(6))

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext

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_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

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

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

    ans_list = []
    count_index = 0
    for num in sorted_data:
        if count_index != num[0]:
            count_index = num[0]
            count_num = 1
        else:
            count_num += 1
        ans_num = str(num[0]).zfill(6) + str(count_num).zfill(6)
        ans_list.append([num[2], ans_num])

    ans_list.sort()

    for ans in ans_list:
        print(ans[1])
 
if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
pre=[[] for _ in range(n)]
for _ in range(m):
    p,y=map(int,input().split())
    pre[p-1].append([y,_,p])
for p in range(n):
    pre[p].sort(key=lambda x:x[0])
    for i in range(len(pre[p])):
        pre[p][i].append(i)
lis=[]
for i in pre:
    for j in i:
        lis.append(j)
lis.sort(key=lambda x:x[1])
for i in lis: print("{:06}{:06}".format(i[2],i[3]+1))

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

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

res = [''] * m
cnt = 1
for i in range(m):
    res[city[i][2]] = str(city[i][0]).zfill(6) + str(cnt).zfill(6)
    if i + 1 < m and city[i][0] == city[i+1][0]:
        cnt += 1
    else:
        cnt = 1


for num in res:
    print(num)

Solution (Python):

import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N, M = zz()
P, Y = [], []
years = defaultdict(list)
ids = defaultdict(list)

for i in range(M):
    p, y = zz()
    years[p].append(y)
    ids[p].append(i)

ans = ['']*M
for p in years:
    c = zip(years[p], ids[p])
    c = sorted(c)
    year, id = zip(*c)
    for i, id_ in enumerate(id):
        i = i + 1
        ans[id_] = str(p).zfill(6) + str(i).zfill(6)
for a in ans:
    print(a)

Solution (Python):
from collections import defaultdict

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

code = [0] * m
ctr = defaultdict(int)
for i in range(m):
    ctr[yp[i][1]] += 1
    x = ctr[yp[i][1]]
    code[yp[i][2]] = '{:06}{:06}'.format(yp[i][1], x)
for c in code:
    print(c)

Solution (Python):


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

py = []
city = {i+1: [] for i in range(n)}
for i in range(m):
    p, y = list(map(int, input().split()))
    city[p].append(y)
    py.append([p, y])


for i in city.values():
    i.sort()


ans = {i+1: {} for i in range(n)}
for key, value in city.items():
    for i in range(len(value)):
        ans[key][value[i]] = i+1

for p, y in py:
    
    print("{:06}{:06}".format(p, ans[p][y]))

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

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


for i in range(M):
    P, Y = map(int, input().split())
    
    Nl[P-1].append({"year": Y, "index": i, "pref": P-1})
newl = []
for i in Nl:
    i.sort(key=lambda x: x["year"])
    num = 1
    for j in i:
        j["order"] = num
        num += 1
    newl += i


newl.sort(key=lambda x: x["index"])

for i in newl:

    print("{:06}".format(i["pref"]+1), end="")
    print("{:06}".format(i["order"]))

Solution (Python):

"""
Created on Sat Jun 20 09:11:30 2020

@author: NEC-PCuser
"""

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 = [-1] * m
for i in range(len(cnt)):
    if not cnt[i]:
        continue
    cnt[i].sort()
    for j in range(len(cnt[i])):
        buf[cnt[i][j][1]] = '{:06d}{:06d}'.format(i, j + 1)
print('\n'.join(buf))

Solution (Python):
n,m = map(int,input().split())
L = [[] for i in range(n)]
ans = [0]*m
l = [list(map(int,input().split())) for i in range(m)]

for i in range(len(l)):
  L[l[i][0]-1].append([l[i][1],i+1])
  
for ind,lis in enumerate(L):
  lis.sort()
  for j in range(len(lis)):
    ans[lis[j][1] - 1] = str(ind+1).zfill(6) + str(j+1).zfill(6)
    
print(*ans,sep = '\n')

Solution (Python):
n,m = map(int,input().split())
L = [[] for i in range(n)]
ans = [None]*m
l = [list(map(int,input().split())) for i in range(m)]

for i in range(len(l)):
  L[l[i][0]-1].append([l[i][1],i+1])
  
for ind,lis in enumerate(L):
  lis.sort()
  for j in range(len(lis)):
    ans[lis[j][1] - 1] = str(ind+1).zfill(6) + str(j+1).zfill(6)
    
print(*ans,sep = '\n')