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

N, M = map(int, input().split())
P = [None] * M
Y = [None] * M
Y_eachP = defaultdict(list)

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


ans = dict()
for p, years in Y_eachP.items():
    years_with_rank = dict(zip(sorted(years), range(1, len(years)+1)))
    ans[p] = years_with_rank

for p, y in zip(P, Y):
    print(str(p).zfill(6) + str(ans[p][y]).zfill(6))

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

P = [0] * M
Y = [0] * M
dic = {}
ano_dic = {}
for m in range(M):
    line = list(map(int, input().split()))
    P[m] = line[0]
    Y[m] = line[1]
    
    dic[m] =[P[m], Y[m]]


ID = {}
count = 0
sorted_list = sorted(dic.items(), key=lambda x: (x[1][0], x[1][1]))



for i, item in enumerate(sorted_list):
    if item[1][0] == sorted_list[i - 1][1][0]:
        count += 1
        ID[item[0]] = str(item[1][0]).zfill(6) + str(count).zfill(6)
    else:
        count = 1
        ID[item[0]] = str(item[1][0]).zfill(6) + str(count).zfill(6)

for item in sorted(ID.items(), key=lambda x: x[0]):
    print(item[1])

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,0])
A.sort(key = lambda x:x[1])
D = dict()
for a in A:
    if a[0] not in D:
        D[a[0]] = 1
    else:
        D[a[0]] += 1
    a[3] = D[a[0]]
A.sort(key=lambda x:x[2])
for a in A:
    print(str(a[0]).zfill(6)+str(a[3]).zfill(6))

Solution (Python):
def resolve():
    (N, M) = list(map(int,input().split(" ")))
    cities = [list(map(int, input().split(" "))) + [i] for i in range(M)]
    sorted_cities = sorted(cities, key=lambda x: (x[0], x[1]))

    pref = 0
    cnt = 0
    for city in sorted_cities:
        if pref != city[0]:
            pref = city[0]
            cnt = 0
        cnt = cnt + 1
        city.append("{:06d}{:06d}".format(pref, cnt))
    
    
    
    

    for city in cities:
        print(city[3])

if '__main__' == __name__:
    resolve()

Solution (Python):
import numpy as np
N, M = map(int, input().split())

x_array = np.array([0] * M)
max_array = np.array([1] * N)



py_array = np.array([list(map(int, input().split())) for i in range(M)])

sorted_index = np.argsort(py_array[:, 1])


for i in sorted_index:
    x_array[i] = max_array[py_array[i][0] - 1]
    max_array[py_array[i][0] - 1] += 1

for x, py in zip(x_array, py_array):
    ans = str(py[0]).zfill(6) + str(x).zfill(6)
    print(ans)

Solution (Python):
def resolve():
    (N, M) = list(map(int,input().split(" ")))
    cities = [list(map(int, input().split(" "))) + [i] for i in range(M)]
    sorted_cities = sorted(cities, key=lambda x: (x[0], x[1]))

    pref = 0
    cnt = 0
    for city in sorted_cities:
        if pref != city[0]:
            pref = city[0]
            cnt = 0
        cnt = cnt + 1
        city.append("{:06d}{:06d}".format(pref, cnt))
    
    sorted_cities = sorted(cities, key=lambda x: x[2])
    for city in sorted_cities:
        print(city[3])
        

if '__main__' == __name__:
    resolve()

Solution (Python):

N , M = input().split()

N = int(N)
M = int(M)


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

PYin.sort()
now = 0
num = 0

for lis in PYin:
    
    if (lis[0] == now) :
        num += 1
        lis.append(num)

    else:
        now = lis[0]
        num = 1
        lis.append(num)


iPn = []

for lis in  PYin:

    iPn.append([ lis[2],lis[0],lis[3] ])

iPn.sort()

for nlis in iPn:

    print (str(nlis[1]).zfill(6) + str(nlis[2]).zfill(6))

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

pref_year_city = [[] for i in range(N)]
for i in range(M):
    pref_year_city[P[i] - 1].append((Y[i], i))

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

ids = ["" for i in range(M)]
for i in range(N):
    for j, (_, city) in enumerate(pref_year_city[i]):
        ids[city] = "{:06d}{:06d}".format(i + 1, j + 1)
        
for i in range(M):
    print(ids[i])

Solution (Python):
import bisect
import operator
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
P, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))

P = np.array(P)
Y = np.array(Y)
order = np.lexsort((Y, P))
P = P[order]
Y = Y[order]

ans = []
cnt = 1
prev = None
for p, y in zip(P, Y):
    if p == prev:
        cnt += 1
    else:
        cnt = 1
    ans.append('{:06d}{:06d}'.format(p, cnt))
    prev = p
print('\n'.join(map(str, np.array(ans)[order.argsort()])))

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

PY.sort(key=lambda x:(x[1],x[2]))
PY[0][2]=1
cnt=1
for i in range(M-1):
    if PY[i+1][1]==PY[i][1]:
        cnt+=1
        PY[i+1][2]=cnt
    else:
        cnt=1
        PY[i+1][2]=cnt
PY.sort(key=lambda x:x[0])
for i in range(M):
    print((("0"*6)+str(PY[i][1]))[-6:]+(("0"*6)+str(PY[i][2]))[-6:])

Solution (Python):
N,M=map(int,input().split())
PY=[[0,0]]
ans=[]
for m in range(M):
    L=list(map(int,input().split()))
    L.append(m+1)
    PY.append(L)
PY.sort(key=lambda x:(x[0],x[1]))

for i in range(M):
    number=""
    if PY[i+1][0]!=PY[i][0]:
        x=1
    else:
        x+=1
    number+=str(PY[i+1][0]).zfill(6)
    number+=str(x).zfill(6)
    ans.append([number,PY[i+1][2]])

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

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

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

Solution (Python):
if __name__ == "__main__":
    _, M = map(int, input().split())
    
    outputs = [0 for _ in range(M)]
    cities = {}

    for i in range(M):
        pref, year = map(int, input().split())
        
        if pref not in cities:
            cities[pref] = {}

        cities[pref][year] = i

    for p in cities:
        city_years = list(cities[p].keys())
        city_years.sort()

        for i, cy in enumerate(city_years):
            outputs[cities[p][cy]] = "{:06}{:06}".format(p, i + 1)

    for line in outputs:
        print(line)

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

for m in range(M):
    PY[m] = [m] + list(map(int, input().split())) + [0] 
    
PY.sort(key = lambda x:x[2])
PY.sort(key = lambda x:x[1])

counter = 1 
for m in range(M):
    if m == 0:
        PY[m][3] = '000001'
    elif PY[m][1] == PY[m-1][1]:
        counter += 1
        l = len(str(counter))
        PY[m][3] = '0'*(6-l)+str(counter)
    else:
        PY[m][3] = '000001'
        counter = 1
        
PY.sort(key = lambda x:x[0])
for m in range(M):
    k = len(str(PY[m][1]))
    print('0'*(6-k)+str(PY[m][1])+str(PY[m][3]))

Solution (Python):
import sys

from collections import deque

from collections import defaultdict

import heapq

import bisect





s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    PY = ii2nnn(M)
    dic = defaultdict(lambda: [])
    for i, (p, y) in enumerate(PY):
        dic[p].append((i, p, y))
    li = []
    for ipy in dic.values():
        ipy.sort(key=lambda v: v[2])
        for j, (i, p, y) in enumerate(ipy):
            li.append((i, p, j+1))
    li.sort(key=lambda v: v[0])
    for i, p, j in li:
        print('%06d%06d' % (p, j))

main()

Solution (Python):
N,M = [int(i) for i in input().split()]
PY = []
for m in range(M):
    PY.append([int(i) for i in input().split()])
    PY[-1].append(m)
PY.sort(key=lambda x:(x[0],x[1]))
ans = []
pre = 0
cnt = 0
for py in PY:
    if pre == py[0]:
        cnt+=1
    else:
        cnt = 1
    ans.append([str(py[0]).zfill(6) + str(cnt).zfill(6),py[2]])
    pre = py[0]
ans.sort(key=lambda x:x[1])
for a in ans:
    print(a[0])

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

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

res = ['']*M
for k, li in sorted(mp.items()):
    for i, (y, l) in enumerate(sorted(li)):
        res[l] = '{:06d}{:06d}'.format(k, i+1)

for st in res: print(st)

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

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

code = ['' for _ in range(M)]

for pp,d in enumerate(yi):
    d.sort()
    for x, (yy,i) in enumerate(d):
        code[i] = "%06d%06d"%(pp+1,x+1)
    
print(*code,sep='\n')

Solution (Python):
N, M = map(int, input().split())
from collections import defaultdict
d = defaultdict(list)
for i in range(M):
    P,Y = map(int, input().split())
    d[P].append([Y,i])
l = [0 for i in range(M)] 
cnt = 0   
for key in d:
    data = sorted(d[key])
    tmp = 0
    for i in range(len(data)):
        l[cnt] = [str(key).zfill(6) + str(tmp+1).zfill(6), data[i][1]]
        cnt += 1
        tmp += 1
l.sort(key = lambda x: x[1])
for i in range(M):
    print(l[i][0])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,m=LI()

  l=[]
  for i in range(m):
    a,b=LI()
    l.append([i,a,b,0])

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

  a=l[0][1]
  b=1
  l[0][3]=b

  for i in range(1,len(l)):
    if a==l[i][1]:
      b+=1
    else:
      a=l[i][1]
      b=1
    l[i][3]=b

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

  for x in l:
    print(str(x[1]).zfill(6)+str(x[3]).zfill(6))

main()

Solution (Python):



from operator import itemgetter


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

citylist = list()

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


citylist.sort(key=itemgetter(2))
citylist.sort(key=itemgetter(1))


wp = ""
for i in range(m):
    if wp != citylist[i][1]:
        ycnt = 1
        wp = citylist[i][1]
    else:
        ycnt += 1
    citylist[i][3] = ycnt

citylist.sort(key=itemgetter(0))

for i in range(m):
    ans1 = str(citylist[i][1]).zfill(6)
    ans2 = str(citylist[i][3]).zfill(6)
    print(ans1+ans2)

Solution (Python):



import sys

input = sys.stdin.readline

def main():
    _ = input()
    m = []
    i = 0
    for l in sys.stdin:
        ar = list(map(int, l.split()))
        ar.append(i)
        m.append(ar)
        i+=1

    m.sort(key=lambda x: (x[0], x[1]))
    right = 1
    for i in range(len(m)):
        if i != 0 and m[i][0] != m[i-1][0]:
            right = 1
        m[i].append("{:0>6}{:0>6}".format(m[i][0], right))
        right += 1

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


main()

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] = "%06d%06d" % (i+1, k+1)
    
print(*ans, sep='\n')

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

convertedPY = [
    {'index': i,
     'city': py[0],
     'year': py[1]
     } for i, py in enumerate(PY)
]
'''
3 4
1 32
3 64
3 63
1 33

'''
convertedPY = sorted(convertedPY, key=lambda a: (a['city'], a['year']))
answer = []
cnt = 0
tmp = convertedPY[0]['city']

result = []
for py in convertedPY:
    
    temp_dict = {}
    if tmp == py['city']:
        cnt += 1
        temp_dict['answer'] = '{:0=6}'.format(py['city']) + '{:0=6}'.format(cnt)
        temp_dict['index'] = py['index']
        result.append(temp_dict)
    else:
        cnt = 1
        temp_dict['answer'] = '{:0=6}'.format(py['city']) + '{:0=6}'.format(cnt)
        temp_dict['index'] = py['index']
        result.append(temp_dict)
        tmp = py['city']


result = sorted(result, key=lambda a: a['index'])

for r in result:
    print(r['answer'])

'''
3
21 -11
81234 52141 94124
'''

Solution (Python):
import bisect
n,m=map(int,input().split())
d=[]
for i in range(m):
     p,y=map(int,input().split())
     d.append([p,y,i])
d=sorted(d,key=lambda x:(x[0],x[1]))
tmp2=[0 for i in range(m)]
p_=0
cnt=0
for x in d:
     p,y,i=x
     if p_!=p:
          p_=p
          cnt=0
     cnt+=1
     tmp2[i]=str(p).zfill(6)+str(cnt).zfill(6)
for x in tmp2:
     print(x)

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

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

prep=0
c=0
dict={}
for city in b:
  p,y,i=city
  if p==prep:
    c+=1
  else:
    c=1
  prep=p
  dict[i]='{0:06d}{1:06d}'.format(p,c)
  
for k,v in dict.items():
  print(v)

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

a = sorted(a)

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

a[-1].append(num)


a = sorted(a, key=lambda x: x[2])
for i in range(m):
    first = str(a[i][0])
    second = str(a[i][3])
    print(first.zfill(6) + second.zfill(6))

Solution (Python):


from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul
from bisect import* 
from heapq import* 
from math import factorial
from copy import deepcopy
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)



def main():
    n,m=map(int,input().split())
    py=[list(map(int,input().split()))+[i]for i in range(m)]
    py=sorted(sorted(py,key=lambda x:x[1]),key=lambda x:x[0])
    d=defaultdict(list)
    pre=py[0][0]
    num=1
    for p,_,i in py:
        if p==pre:
            d[i]=[p,num]
            num+=1
        else:
            num=2
            pre=p
            d[i]=[p,1]

    for i in range(m):
        s,t=d[i]
        print(str(s).zfill(6)+str(t).zfill(6))

    
if __name__ == '__main__':
    main()

Solution (Python):


from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul
from bisect import* 
from heapq import* 
from math import factorial
from copy import deepcopy
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)



def main():
    n,m=map(int,input().split())
    py=[list(map(int,input().split()))+[i]for i in range(m)]
    py=sorted(sorted(py,key=lambda x:x[1]),key=lambda x:x[0])
    d=defaultdict(list)
    pre=py[0][0]
    num=1
    for p,_,i in py:
        if p==pre:
            d[i]=[p,num]
            num+=1
        else:
            num=2
            pre=p
            d[i]=[p,1]

    for i in range(m):
        s,t=d[i]
        print(str(s).zfill(6)+str(t).zfill(6))

    
if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
l = [None] * M
for i in range(M):
	p, y = map(int, input().split())
	l[i] = [p, y, i]
l.sort()
ans = []
t = l[0][0]
x = 0
for i in l:
	if t == i[0]:
		x += 1
		ans.append([i[2], i[0], x])
	else:
		t = i[0]
		x = 1
		ans.append([i[2], i[0], x])
ans.sort()
for i in ans:
	p = str(i[1])
	x = str(i[2])
	print('0' * (6 - len(p)) + p + '0' * (6 - len(x)) + x)

Solution (Python):
n,m=map(int,input().split())
ids=[list(map(int,input().split())) for i in range(m)]
for i in range(m):
    ids[i].append(i)
ids.sort()
ans=[]
tmp=ids[0][0]
x=0
for i in ids:
    if tmp==i[0]:
        x+=1
        ans.append([i[2],i[0],x])
    else:
        tmp=i[0]
        x=1
        ans.append([i[2],i[0],x])
ans.sort()        
for i in ans:
    p,x=str(i[1]).zfill(6),str(i[2]).zfill(6)
    print(p,x,sep='')

Solution (Python):
N,M = (int(i) for i in input().split())
e = [tuple([int(i) for i in input().split()]) for i in range(M)]
d = {}
for k,v in e:
    if k in d.keys():  d[k].append(v)
    else:   d[k] = [v]
ans_dict = {}
for k,v in d.items():
    v.sort()
    r = str(k).zfill(6)
    for i in range(len(v)):
        ans_dict[(k,v[i])] = r+str(i+1).zfill(6)
for ans in e:
    print(ans_dict[ans])

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

n, m = map(int, input().split())
ans = [""] * m
arr = []
cnt = 1
for i in range(m):
    p, y = map(int, input().split())
    arr.append((p, y, i))
arr.sort()

ans[arr[0][2]] = "{:06}{:06}".format(arr[0][0], cnt)
for i in range(1, m):
    if arr[i - 1][0] == arr[i][0]:
        cnt += 1
    else:
        cnt = 1
    ans[arr[i][2]] = "{:06}{:06}".format(arr[i][0], cnt)

for i in ans:
    print(i)

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

n, m = list(map(int, input().rstrip().split()))
ans = [""] * m
arr = []
cnt = 1
for i in range(m):
    p, y = map(int, input().split())
    arr += [(p, y, i)]
arr = sorted(arr)

ans[arr[0][2]] = "{:06}{:06}".format(arr[0][0], cnt)
for i in range(1, m):
    if arr[i - 1][0] == arr[i][0]:
        cnt += 1
    else:
        cnt = 1
    ans[arr[i][2]] = "{:06}{:06}".format(arr[i][0], cnt)

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

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

n, m = list(map(int, input().rstrip().split()))
ans = [""] * m
arr = []
cnt = 1
for i in range(m):
    p, y = map(int, input().split())
    arr += [(p, y, i)]
arr = sorted(arr)

ans[arr[0][2]] = "{:06}{:06}".format(arr[0][0], cnt)
for i in range(1, m):
    if arr[i - 1][0] == arr[i][0]:
        cnt += 1
    else:
        cnt = 1
    ans[arr[i][2]] = "{:06}{:06}".format(arr[i][0], cnt)

for i in ans:
    print(i)

Solution (Python):
N, M = map(int, input().split())
C = [tuple(map(int, input().split())) for _ in range(M)]
P = {c[0]: [] for c in C}
for c in C:
    P[c[0]].append(c[1])
for p in P:
    P[p].sort()
    P[p] = {P[p][i]: i + 1 for i in range(len(P[p]))}
for c in C:
    print('{:06}{:06}'.format(c[0], P[c[0]][c[1]]))

Solution (Python):
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
A = [i for i in range(1, M + 1)]
tL = list(zip(*L))
P = tL[0]
Y = tL[1]
Z = list(zip(A, P, Y))
sortedZ = sorted(Z, key=lambda x:x[2])
count= {}
X = []
for i in range(M):
    count.setdefault(sortedZ[i][1], 0)
    count[sortedZ[i][1]] = count[sortedZ[i][1]] + 1
    X.append(count[sortedZ[i][1]])
T = list(zip(*sortedZ))
GOD = list(zip(T[0], T[1], T[2], X))
ans = sorted(GOD)
for i in range(M):
    print(str(ans[i][1]).rjust(6, '0') + str(ans[i][3]).rjust(6, '0'))

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

L = [[i+1,0,0,0] for i in range(n)]

for i in range(n):
    L[i][1],L[i][2] = map(int,input().split())

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

cnt = 1
for i in range(n):
    if i != 0 and L[i][1] != L[i-1][1]:
        cnt = 1
    L[i][3] = str(1000000+L[i][1])[1:7] + str(1000000+cnt)[1:7]
    cnt += 1

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

for i in range(n):
    print(L[i][3])

Solution (Python):

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



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


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



city_number = [""] * M
city_count_in_prefecture = 1
for i in range(M):
    if i == 0:  
        city_number[city_list[i][0]] = str(city_list[i][1]).zfill(6) + str(city_count_in_prefecture).zfill(6)
    elif city_list[i][1] == city_list[i - 1][1]:  
        city_count_in_prefecture += 1
        city_number[city_list[i][0]] = str(city_list[i][1]).zfill(6) + str(city_count_in_prefecture).zfill(6)
    else:  
        city_count_in_prefecture = 1
        city_number[city_list[i][0]] = str(city_list[i][1]).zfill(6) + str(city_count_in_prefecture).zfill(6)


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

Solution (Python):
N, M = map(int, input().split())
city_list = []
for i in range(M):
    a,b = map(int,input().split())
    city_list.append([a,b,0,i])

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

city_id = 1
city_cnt = 1
i = 0

while True:
    if i + 1 > M:
        break

    elif city_id == city_list[i][0]:
        city_list[i][2] = city_cnt
        city_cnt += 1
        i += 1
    
    elif city_id <= N+1:
        city_cnt = 1
        city_id += 1

    else:
        break
            
city_list.sort(key=lambda city_list:city_list[3])

for city in city_list:
    print('{:0>6}{:0>6}'.format(city[0],city[2]))

Solution (Python):
n,m=map(int,input().split())
p = []
for i in range(m):
    p1= list(map(int,input().split()))
    p.append(p1 + [i])
p2 = sorted(p,key=lambda x:(x[0],x[1]))
p3 = []
pref = 0
state = 0
for j in p2:
    if j[0] != pref:
        pref = j[0]
        state = 1
        p3.append([j[0],j[1],j[2],str(j[0]).rjust(6, '0')+str(state).rjust(6,'0')])
    else:
        state += 1
        p3.append([j[0],j[1],j[2],str(j[0]).rjust(6, '0')+str(state).rjust(6,'0')])
p3.sort(key = lambda x:(x[2]))
for i in p3:
    print(i[3])

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

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

cnt = [0] * (N + 1)
ans = [""] * M

for p, y, i in PY:
    
    cnt[p] += 1
    
    ans[i] = str(p).zfill(6) + str(cnt[p]).zfill(6)

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

Solution (Python):
import bisect
from collections import defaultdict
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
C=[]
D=defaultdict(list)
for i in range(m):
  p,y=map(int,input().split())
  C.append([p,y])
  D[p].append(y)
for k in D.keys():
  D[k].sort()
for i in range(m):
  y=bisect.bisect_left(D[C[i][0]],C[i][1])+1
  print(str(C[i][0]).zfill(6)+str(y).zfill(6))

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


PY.sort(key=lambda x:(x[2],x[3]))

p = -1
num = 1
for i,py in enumerate(PY):
  if p != py[2]:
    p = py[2]
    num = 1
    PY[i][1] = num
  else:
    num += 1
    PY[i][1] = num

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

for py in PY:
  print('{:0=6}{:0=6}'.format(py[2], py[1]))

Solution (Python):
n,m = map(int,input().split())
D = dict()
A = []
for i in range(m):
    p,y = map(int,input().split())
    A.append([p,y,i,0])
A.sort(key = lambda x:x[1])
for a in A:
    if a[0] not in D:
        D[a[0]] = 1
    else:
        D[a[0]] +=1
    a[3] = D[a[0]]
A.sort(key = lambda x:x[2])
for a in A:
    print(str(a[0]).zfill(6)+str(a[3]).zfill(6))

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

PY_copy = [PY[i] + [i] for i in range(M)]
PY_copy = sorted(PY_copy, key=lambda x:(x[0],x[1]))

order = 0
previous_prefecture = PY_copy[0][0]
for i in range(M):
  if PY_copy[i][0] == previous_prefecture:
    order += 1
  else:
    previous_prefecture = PY_copy[i][0]
    order = 1
  PY_copy[i] = PY_copy[i] + [order]

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


for i in range(M):
  P_zfill = str(PY_copy[i][0]).zfill(6)
  order_zfill = str(PY_copy[i][3]).zfill(6)
  print(P_zfill + order_zfill)

Solution (Python):
n,m=map(int,input().split())
city=list(list(map(int,input().split()))+[i] for i in range(m))
city.sort(key=lambda x:x[1])
city.sort(key=lambda x:x[0])
for j,l in enumerate(city):
    if j!=0 and city[j-1][0]==city[j][0]:
        city[j].append(city[j-1][3]+1)
    elif j!=0 and city[j-1][0]!=city[j][0]:
        city[j].append(1)
    else:
        city[j].append(1)
city.sort(key=lambda x:x[2])
for k in range(m):
    print('{0:06d}{1:06d}'.format(city[k][0],city[k][3]))

Solution (Python):
N,M=map(int,input().split())
PY=list(list(map(int,input().split()))+[i] for i in range(M))
PY.sort(key=lambda x:x[1])
PY.sort(key=lambda x:x[0])
for j,J in enumerate(PY):
    if j!=0 and PY[j-1][0]==PY[j][0]:
        PY[j].append(PY[j-1][3]+1)
    elif j!=0 and PY[j-1][0]!=PY[j][0]:
        PY[j].append(1)
    else:
        PY[j].append(1)
PY.sort(key=lambda x :x[2])
for k in range(M):
    print('{0:06d}{1:06d}'.format(PY[k][0],PY[k][3]))

Solution (Python):
import bisect

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

pn_cn = []
pn_cn_dict = {}


for _ in range(m):
    pn, cn = map(int, input().split())
    cities = pn_cn_dict.get(pn)
    if cities is None:
        cities = [cn]
    else:
        cities.append(cn)
    pn_cn_dict[pn] = cities
    pn_cn.append((pn, cn))

for k in pn_cn_dict:
    c = pn_cn_dict[k]
    c = sorted(c)
    pn_cn_dict[k] = c

for pn, cn in pn_cn:
    ci = bisect.bisect(pn_cn_dict[pn], cn)
    print("{:06}{:06}".format(pn, ci))

Solution (Python):
import bisect

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

pn_cn = []
pn_cn_dict = {}


for _ in range(m):
    pn, cn = map(int, input().split())
    cities = pn_cn_dict.get(pn)
    if cities is None:
        cities = [cn]
    else:
        cities.append(cn)
    pn_cn_dict[pn] = cities
    pn_cn.append((pn, cn))

for k in pn_cn_dict:
    c = pn_cn_dict[k]
    c = sorted(c)
    pn_cn_dict[k] = c

for pn, cn in pn_cn:
    ci = bisect.bisect(pn_cn_dict[pn], cn)
    print("{:06}{:06}".format(pn, ci))

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

counter = -1
prev_pref = -1
for city in sorted(birth_list, key=lambda x: (x[0], x[1])):
    
    if city[0] != prev_pref:
        counter = 1
    else:
        counter += 1
    identity_number = str(city[0]).zfill(6) + str(counter).zfill(6)
    city.append(identity_number)
    prev_pref = city[0]

for city in birth_list:
    print(city[2])

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

PY = [[0]*4]*M
p_dict = {}
for i in range(M):
    p, y = map(int,input().split())
    
    if p not in p_dict.keys():
        p_dict[p] = [[p, y, i]]
    else:
        p_dict[p].append([p, y, i])

ans = []
for p in p_dict.keys():
    p_dict[p].sort()
    for i in range(len(p_dict[p])):
        ans.append(p_dict[p][i] + [i+1])
 
ans.sort(key=lambda x: x[2])

for i in range(M):
    print("{:06d}{:06d}".format(ans[i][0], ans[i][3]))

Solution (Python):

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

PY = [[0]*4]*M
p_dict = {}
for i in range(M):
    p, y = map(int,input().split())
    
    if p not in p_dict.keys():
        p_dict[p] = [[p, y, i]]
    else:
        p_dict[p].append([p, y, i])

ans = []
for p in p_dict.keys():
    p_dict[p].sort()
    for i in range(len(p_dict[p])):
        ans.append(p_dict[p][i] + [i+1])
 
ans.sort(key=lambda x: x[2])

for i in range(M):
    print("{:06d}{:06d}".format(ans[i][0], ans[i][3]))

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

ans = [' ']*M
num = [1]*N

for i, v in sorted(enumerate(List), key=lambda x: (x[1][0], x[1][1])):
    ans[i] = '{:06}{:06}'.format(v[0], num[v[0]-1])
    num[v[0]-1] += 1
    
print('\n'.join(ans))

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

city = py[0][1]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        num = 1
        city = i[1]
    i.append(num)

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

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

Solution (Python):
"""



"""

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

city = [list(map(int, input().split())) + [i] + [0] for i in range(M)]

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

for m in range(M):
    if m == 0:
        city[m][3] = 1
    elif city[m][0] != city[m - 1][0]:
        city[m][3] = 1
    else:
        city[m][3] = city[m - 1][3] + 1

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

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

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

city = py[0][1]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        num = 1
        city = i[1]
    i.append(num)

py.sort()

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

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

city = py[0][1]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        city = i[1]
        num = 1
    i.append(num)

py.sort()

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

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

PY = sorted(PY)

keyP = -1
for i, (P, Y, _) in enumerate(PY):
  if keyP != P:
    keyP = P
    keyNo = 1

  PY[i].append("{:0>6}{:0>6}".format(keyP, keyNo))
  keyNo += 1

for P, Y, _, s in sorted(PY, key=lambda x:x[2]):
  print(s)

Solution (Python):
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
ans = [''] * M
num = [1] * N

for i, v in sorted(enumerate(X), key=lambda x: (x[1][0], x[1][1])):
    ans[i] = '{:06}{:06}'.format(v[0], num[v[0] - 1])
    num[v[0] - 1] += 1
    
print('\n'.join(ans))

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

city = X[0][1]
num = 0
for v in X:
    if city == v[1]:
        num += 1
    else:
        city = v[1]
        num = 1
    v.append(num)

X.sort()
for v in X:
    print('{:06}{:06}'.format(v[1], v[3]))