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):
list1 = input().split()
n = int(list1[0])
m = int(list1[1])
pre = [[] for i in range(n)]

for j in range(m):
    data = input().split()
    p = int(data[0])
    y = int(data[1])
    pre[p - 1].append((j, y))

inums = []
for k in range(n):
    if len(pre[k]) == 0:
        pass
    else:
        sorted_y = sorted(pre[k], key = lambda x:x[1])
        for l in range(len(sorted_y)):
            s1 = str(k + 1).zfill(6)
            s2 = str(l + 1).zfill(6)
            inums.append((sorted_y[l][0], s1 + s2))

ans = sorted(inums, key = lambda x:x[0])
for h in range(m):
    print(ans[h][1])

Solution (Python):
import bisect

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

p, y = [], []
for _ in range(m):
    temp = [int(_) for _ in input().split(' ')]
    p.append(temp[0])
    y.append(temp[1])
ys = dict()
for i in range(m):
    if not(p[i] in ys):
        ys[p[i]] = []
    ys[p[i]].append(y[i])

for j in ys.keys():
    ys[j].sort()

for i in range(m):
    print('{0}{1}'.format(str(p[i]).zfill(6), str(bisect.bisect(ys[p[i]], y[i])).zfill(6)))

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

l1 = [[] for i in range(n)]
l2 = []

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

dic = {}

for p in range(n):
    l1[p].sort()
    for i in range(len(l1[p])):
        dic[l1[p][i]] = i+1
        

for i in range(m):
    p = l2[i][0]
    k = dic[l2[i][1]]
    p = str(p)
    k = str(k)
    ans = "0"*(6-len(p))+p+"0"*(6-len(k))+k
    print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import defaultdict
n, m = map(int, input().split())
ans = [""] * m
li = []
for i in range(m):
    p, y = map(int, readline().split())
    li.append((p, y, i))
li.sort()
cnt = 1
ans[li[0][2]] = "{:06}{:06}".format(li[0][0], cnt)
for i in range(1, m):
    cnt = cnt + 1 if li[i - 1][0] == li[i][0] else 1
    ans[li[i][2]] = "{:06}{:06}".format(li[i][0], cnt)
print(*ans, sep="\n")

Solution (Python):
n, m = map(int, input().split())
ans = [""] * m
li = []
for i in range(m):
    p, y = map(int, input().split())
    li.append((p, y, i))
li.sort()
cnt = 1
ans[li[0][2]] = "{:06}{:06}".format(li[0][0], cnt)
for i in range(1, m):
    cnt = cnt + 1 if li[i - 1][0] == li[i][0] else 1
    ans[li[i][2]] = "{:06}{:06}".format(li[i][0], cnt)
print(*ans, sep="\n")

Solution (Python):
n, m = map(int, raw_input().split())
arr = []
for i in range(m):
    pi, yi = map(int, raw_input().split())
    arr.append([pi, yi, i+1])

def six_digit(n):
    if len(str(n)) < 6:
        n = "0"*(6-len(str(n)))+str(n)
    else:
        n=str(n)
    return n
arr.sort()
cp = 1
num = 0
for lst in arr:
    if lst[0]!=cp:
        cp=lst[0]
        num = 1
    else:
        num += 1
    lst.reverse()
    id = six_digit(cp)+six_digit(num)
    lst.append(id)

arr.sort()
for lst in arr:
    print lst[3]

Solution (Python):
from operator import itemgetter
n,m = map(int,input().split())
lis = []
ans = [0 for i in range(m)]
num = [0 for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  lis.append([i,a,b])
lis.sort(key=itemgetter(2))
for i in range(m):
  num[lis[i][1]-1] += 1
  cou = max(0,5-(lis[i][1] // 10))
  co = max(0,5-(num[lis[i][1]-1] // 10))
  ans[lis[i][0]] = format(lis[i][1],'06d') + format(num[lis[i][1]-1],'06d')
for i in range(m):print(ans[i])

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

N,M=[int(n) for n in input().split()]
lis=[[i]+[int(n) for n in input().split()] for i in range(M)]

l_2=sorted(lis, key=lambda x: x[2])
dic={}
for k,i,j in l_2:
    dic[i]=dic.get(i,0)+1
    lis[k]='{:0=6}{:0=6}'.format(i,dic[i])
for i in lis:print(i)

Solution (Python):
def main():
    n, m = map(int, input().split())
    lines = [input() for j in range(m)]
 
    cities = {}
    for i in range(m):
        p, y = map(int, lines[i].split())
        if p in cities:
            cities[p].append((i, y))
        else:
            cities[p] = [(i, y)]
 
    outputs = [None] * m
    for pref, city_list in cities.items():
        city_list.sort(key=lambda x: x[1])
        
        city_no = 1
        for city in city_list:
            outputs[city[0]] = "{:06d}{:06d}".format(pref, city_no)
            city_no += 1
 
    for output in outputs:
        print(output)
    return
 
 
main()

Solution (Python):

class ipy:
    def __init__(self, i, p, y):
        
        self.i = i
        
        self.p = p
        
        self.y = y


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

list_ipy = []

for i in range(M):
    p, y = map(int, input().split())
    list_ipy.append(ipy(i, p, y))

list_ipy.sort(key=lambda x: x.y)

p_count = {}

out = {}

for x in list_ipy:
    
    if x.p in p_count:
        p_count[x.p] += 1
    else:
        p_count[x.p] = 1
    
    out[x.i] = [x.p, p_count[x.p]]

for k in out:
    print('{0:06d}{1:06d}'.format(out[k][0], out[k][1]))

Solution (Python):
class ipy:
    def __init__(self, i, p, y):
        self.i = i
        self.p = p
        self.y = y


N, M = map(int, input().split())
list_ipy = []
for i in range(M):
    p, y = map(int, input().split())
    list_ipy.append(ipy(i, p, y))
list_ipy.sort(key=lambda x: x.y)
p_ord = {}
out = {}
for x in list_ipy:
    if x.p in p_ord:
        p_ord[x.p] += 1
    else:
        p_ord[x.p] = 1
    out[x.i] = [x.p, p_ord[x.p]]
for k in out:
    print('{0:06d}{1:06d}'.format(out[k][0], out[k][1]))

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

from operator import itemgetter
for i in range(0,n+1):
    l[i].sort(key=itemgetter(1))

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

for i in range(0,n+1):
    for index,(city,y)in enumerate(l[i]):
        i = str(i)
        if 6-len(i)!=0:
            i = "0"*(6-len(i)) + i
        index = str(index+1)
        if 6-len(index)!=0:
            index = "0"*(6-len(index)) + index
        ans[city] = i+index
for i in range(1,m+1):
    print(ans[i])

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

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

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

ans = []

for p in range(n):
    pyi[p].sort()
    for j in range(len(pyi[p])):
        y, i = pyi[p][j]
        ans.append((i, str(p + 1).zfill(6) + str(j + 1).zfill(6)))

ans.sort()
for a in ans:
    print(a[1])

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

tmp = []
res = ['' for i in range(M)]
count = [1 for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    tmp.append([A,B,i])

tmp.sort(key=lambda tmp: tmp[1])

for i in range(M):
    res[tmp[i][2]] += '0'*(6-len(str(tmp[i][0]))) + str(tmp[i][0]) + '0'*(6-len(str(count[tmp[i][0]]))) + str(count[tmp[i][0]])
    count[tmp[i][0]] += 1

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

Solution (Python):

def ABC113C():

    N, M = map(int, input().split())
    PY = [list(map(int, input().split())) for i in range(M)]
    P = [[] for i in range(10 ** 5)]

    from operator import itemgetter
    
    for k in range(len(PY)):
        i = PY[k][0]
        j = PY[k][1]
        P[i - 1].append([j, k])

    for i in range(len(P)):
        P[i].sort()

    anslist = []
    for i in range(len(P)):
        for j in range(len(P[i])):
            anslist.append([i + 1, j + 1, P[i][j][1] + 1])
    anslist.sort(key = itemgetter(2))
    for i, j, k in anslist:
        i = str(i)
        j = str(j)
        while len(i) != 6:
            i = "0" + i
        while len(j) != 6:
            j = "0" + j
        print(i + j)
ABC113C()

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

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

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

for i, (p, y) in enumerate(a):
    cities[p-1].append((y, i))

ans = [None]*m
for p in range(n):
    for j, (y, i) in enumerate(sorted(cities[p])):
        tmp = str(p+1).zfill(6) + str(j+1).zfill(6)
        ans[i] = tmp

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

Solution (Python):
from operator import itemgetter

N,M=map(int,input().split())
PY=[]
ans=[0 for i in range(M)]
cc=[0 for i in range(N)]
for i in range(M):
    PYi=list(map(int,input().split()))
    PY.append([i,PYi[0],PYi[1]])
     
PY=sorted(PY, key=itemgetter(2))

for i in range(M):
    cc[PY[i][1]-1]+=1
    ans[PY[i][0]]=format(PY[i][1],'06d')+format(cc[PY[i][1]-1],'06d')

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

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

lists = [ ]

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

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

bef = 0
state = 0
retstr = ''
triple = [ ]
for i in lists:
    if (i[ 0 ] != bef):
        bef = i[ 0 ]
        state = 1
        triple.append ( [ i[ 0 ], i[ 1 ], i[ 2 ], str ( i[ 0 ] ).rjust ( 6, '0' ) + str ( state ).rjust ( 6, '0' ) ] )
    else:
        state += 1
        triple.append ( [ i[ 0 ], i[ 1 ], i[ 2 ], str ( i[ 0 ] ).rjust ( 6, '0' ) + str ( state ).rjust ( 6, '0' ) ] )

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

Solution (Python):
def ume(s):
    while(len(s) <6):
        s = '0' + s
    return s

N, M = [int(i) for i in input().split()]

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

ans = []
for i in range(1,N+1):
    A[i].sort()
    upper = ume(str(i))
    for j in range(1,len(A[i])+1):
        lower = ume(str(j))
        ans.append((A[i][j-1][1] ,upper+lower))

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

Solution (Python):
import bisect
N, M = map(int, input().split())
P, Y = [], []
pref = [[] for _ in range(N+1)] 
for m in range(M):
    p,y = map(int, input().split())
    P.append(p)
    Y.append(y)
    pref[p].append(y)
for i, p in enumerate(pref):
    pref[i] = sorted(p)
    
for p,y in zip(P,Y):
    ans = "{:0>6}".format(p)
    i = bisect.bisect(pref[p], y)
    ans += "{:0>6}".format(i)
    print(ans)

Solution (Python):
import bisect
N, M = map(int, input().split())
P, Y = [], []
pref = [[] for _ in range(N+1)] 
for m in range(M):
    p,y = map(int, input().split())
    P.append(p)
    Y.append(y)
    pref[p].append(y)

for i,pre in enumerate(pref):
    pref[i] = sorted(pre)

for p,y in zip(P,Y):
    a = "{:0>6}".format(p)
    i = bisect.bisect(pref[p], y)
    a += "{:0>6}".format(i)
    print(a)

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


p_count  = [0 for i in range(N)]

l_2 = []
for i in range(M):
	p_count[l[i][1]-1] += 1
	l_2.append((l[i][2], l[i][1], p_count[l[i][1]-1]))
l_2.sort()
for i in range(M):
	print(str(l_2[i][1]).zfill(6)+str(l_2[i][2]).zfill(6))

Solution (Python):
from operator import itemgetter
N, M = map(int, input().split())

A = []
for i in range(M):
  A.append([i] + list(map(int, input().split())) + ["x"])

A.sort(key=itemgetter(1,2))

keynum, count = 0, 1
for i in range(M):
  if keynum != A[i][1]:
    keynum = A[i][1]
    count = 1
  else:
    count += 1
    
  A[i][3] = str(keynum).zfill(6) + str(count).zfill(6)
  
A.sort(key=itemgetter(0))
for i in range(M):
  print(A[i][3])

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())
X=sorted([(Y[i],P[i],i) for i in range(M)])
Z=[(0,0) for i in range(M)]
T=[0 for i in range(N)]
for i in range(M):
    T[X[i][1]-1]+=1
    Z[X[i][2]]=(X[i][1],T[X[i][1]-1])
for seq in Z:
    a=max(0,6-len(str(seq[0])))
    b=max(0,6-len(str(seq[1])))
    print("0"*a+str(seq[0])+"0"*b+str(seq[1]))

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

for i in range(len(pref)):
        for j in range(len(pref[i])):
                ans[pref[i][j][1]] = [i+1,j+1]

for i in range(len(ans)):
        print("%06d%06d"%(ans[i][0],ans[i][1]))

Solution (Python):
from collections import defaultdict as dd

d=dd(int)
n,m=map(int,input().split())
l=[[i]+list(map(int,input().split()))+[0] for i in range(m)]

o=sorted(l,key=lambda x:x[2])
for i,j in enumerate(o):
  d[j[1]]+=1
  o[i][3]=d[j[1]]

for i in sorted(o):
  print("%06d%06d"%(i[1],i[3]))

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

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

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

ans = []

for pre_id, info in enumerate(PY):
    info.sort()
    for i in range(len(info)):
        ans.append((info[i][1], "%06d" % pre_id, "%06d" % (i + 1)))

ans.sort()
for i, x, y in ans:
    print(str(x) + str(y))

Solution (Python):
from operator import attrgetter


class City:
    def __init__(self, p, y):
        self.p = p
        self.y = y

    def set_num(self, n):
        self.n = '{0:06d}'.format(self.p) + '{0:06d}'.format(n)


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

pref_map = {}
for city in cities:
    if city.p in pref_map:
        pref_map[city.p].append(city)
    else:
        pref_map[city.p] = [city]

for v in pref_map.values():
    _cities = sorted(v, key=attrgetter("y"))
    cnt = 1
    for _city in _cities:
        _city.set_num(cnt)
        cnt += 1

for city in cities:
    print(city.n)

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

a,b = map(int,input().split())
aa = []
d = []
for i in range(b):
    k,kk = map(int,input().split())
    d.append([k, kk,i+1])

da = sorted(d)

kkk = da[0][0]
ll = 0
for i in range(b):
    kkkk = da[i][0]
    if kkk == kkkk:
        ll += 1
    else:
        kkk = kkkk
        ll = 1
    aa.append([da[i][2],da[i][0],ll])
aa.sort()

for i in aa:
    m = str(i[1])
    n = str(i[2])
    m = "0"*(6-len(m))+m
    n = "0"*(6-len(n))+n
    print(m+n)

Solution (Python):
n,m  = list(map(int,input().split()))
tmpa = [[] for _ in range(n)]
pyxs = []
i_id = [0] * (n+1)
ans  = [None] * m 

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

for p,y,x in pyxs:
    i_id[p] += 1
    ans[x] = '{:06}'.format(p) + '{:06}'.format(i_id[p])

for s in ans:
    print(s)

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

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

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

num = [0] * (n+1)
ans = [None]*m

for p, y, x in pyxs:
    ans[x] = '{:06}'.format(p) + '{:06}'.format(num[p]+1)
    num[p] += 1

for s in ans:
    print(s)

Solution (Python):
from itertools import chain


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

P = [0] * N

I = list(range(M))

Q = [None] * M
Y = [None] * M

for m in range(M):
    Q[m], Y[m] = map(int, input().split())
    P[Q[m]-1] += 1

D = zip(I, Q, Y)
D = sorted(D, key=lambda x: [x[1], x[2]])
I, Q, Y = map(list, zip(*D))

P = list(chain.from_iterable([list(range(1, p+1)) for p in P]))

D = zip(I, Q, Y, P)
D = sorted(D, key=lambda x: x[0])
I, Q, Y, P = map(list, zip(*D))

for i in range(M):
    print('%06d%06d' % (Q[i], P[i]))

Solution (Python):
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)


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


Cities = []

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

Cities.sort()
PsCount = {}


ans = []

for c in Cities:
	if c[1] in PsCount:
		PsCount[c[1]] += 1
		ans.append([c[2], c[1], PsCount[c[1]]])
	else:
		PsCount[c[1]] = 1
		ans.append([c[2], c[1], 1])

ans.sort()


for elem in ans:
	print(str(elem[1]).zfill(6)+str(elem[2]).zfill(6))

Solution (Python):
def c_id(N, M, City):
    
    
    city = sorted(City, key=lambda x: (x[0], x[1]))

    checking_city_num = city[0][0]  
    x = 1  
    for j, (p, y, k) in enumerate(city):
        if p == checking_city_num:  
            city[j] = [p, x, k]
            x += 1  
        else:
            checking_city_num = p  
            city[j] = [p, 1, k]
            x = 2  

    ans_tmp = []
    
    for p, q, k in sorted(city, key=lambda x: x[2]):
        ans_tmp.append('{0:06d}{1:06d}'.format(p, q))
    ans = '\n'.join(ans_tmp)
    return ans

N, M = [int(i) for i in input().split()]
City = [[int(i) for i in input().split()] + [k] for j, k in enumerate(range(M), 1)]
print(c_id(N, M, City))

Solution (Python):
n,m = map(int,input().split())
d = dict()
p = [0]*m
y = [0]*m
c = [0]*m
a = []
for i in range(m):
  p[i], y[i] = map(int,input().split())
  a.append([y[i], i, p[i]])
a.sort()
for x in a:
  if x[2] in d:
    d[x[2]] =  d[x[2]] + 1
  else:
    d[x[2]] = 1
  c[x[1]] = d[x[2]]
for i in range(m):
  print("{0:06d}".format(p[i])+"{0:06d}".format(c[i]))

Solution (Python):
I=lambda:list(map(int,input().split()[::-1]))
m,n=I()
c=[0]*-~n
a=[0]*m
for y,p,i in sorted(I()+[i]for i in range(m)):
  c[p]+=1
  a[i]='%06d%06d'%(p,c[p])
print('\n'.join(a))

Solution (Python):
N = input().split()
count = [0] * int(int(N[0])+1)
P = []
ans = []

for i in range(int(N[1])):
	p,y = map(int, input().split())
	P.append(list([p,y,i]))
K = sorted(P)
for i, n in enumerate(K):
	count[int(n[0])]+=1
	ans.append(list([n[2],n[0],count[int(n[0])]]))

ans.sort()
for i, n in enumerate(ans):
	print("{:0=6}".format(int(n[1])) + "{:0=6}".format(int(n[2])))

Solution (Python):

import sys

import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

n, m = map(int, input().split())
p = defaultdict(lambda :defaultdict(list))
e = [[int(i) for i in input().split()] for i in range(m)] 
p_index = defaultdict(int)
for i in e:
    pp, yy = i[0], i[1]
    p[pp][yy] = 0

for i in p:
    count = 0
    l = sorted(p[i])
    for j in l:
        count += 1
        p[i][j] += count

for i in e:
    print("{:0=6}".format(i[0]) + "{:0=6}".format(p[i[0]][i[1]]))

Solution (Python):

from sys import stdin
from operator import itemgetter

N,M = [int(x) for x in stdin.readline().rstrip().split()]
counter = 0
country = 1

ID = []

for i in range(M):
    p,y = [int(x) for x in stdin.readline().rstrip().split()]
    ID.append([p,y,i,"no"])
ID.sort(key=itemgetter(0,1))

for i in range(M):
    if ID[i][0] != country:
        counter = 0
    country = ID[i][0]
    counter += 1
    ID_m = format(ID[i][0],"06") + format(counter,"06")
    ID[i][3] = ID_m
    
ID.sort(key=itemgetter(2))

for i in range(M):
    print(ID[i][3])

Solution (Python):
I=lambda:list(map(int,input().split()))[::-1];m,n=I();c=[0]*-~n;a=[0]*m
for y,p,i in sorted(I()+[i]for i in range(m)):c[p]+=1;a[i]='%06d%06d'%(p,c[p])
print('\n'.join(a))

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

l1 = [[] for i in range(n)]
l2 = []

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

for p in range(n):
    l1[p].sort()

for i in range(m):
    p = l2[i][0]
    k = bisect.bisect_right(l1[p-1],l2[i][1])
    p = str(p)
    k = str(k)
    ans = "0"*(6-len(p))+p+"0"*(6-len(k))+k
    print(ans)

Solution (Python):
I=lambda:list(map(int,input().split()))[::-1];m,n=I();c=[0]*-~n;a=[0]*m
for y,p,i in sorted(I()+[i]for i in range(m)):c[p]+=1;a[i]='%06d'%p+'%06d'%c[p]
for t in a:print(t)

Solution (Python):
N, M = map(int, input().split())
pres = {}
cities = {}

for i in range(1, N + 1):
    pres[i] = []

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

for i in range(1, N + 1):
    pre = pres[i]
    if len(pre) > 0:
        pre.sort(key=lambda city: cities[city][1])
        for j in range(0, len(pre)):
            cities[pre[j]].append(j + 1)

for i in range(1, M + 1):
    city = cities[i]
    print("{:06d}{:06d}".format(city[0], city[2]))

Solution (Python):
N = input().split()
count = [0] * int(int(N[0])+1)
P = []
ans = []
for i in range(int(N[1])):
	p,y = map(int, input().split())
	P.append((y,p,i))

K = sorted(P)

for y,p,i in K:
	count[p] += 1
	ans.append((i,p,count[p]))

ans.sort()
for i,p,count in ans:
	print("{:0=6}".format(int(p))+"{:0=6}".format(count))

Solution (Python):
n,m = map(int,input().split())
s = [list(map(int,input().split()))+[i] for i in range(m)]
s.sort()
l = [[] for i in range(n)]
for e in s:
    l[e[0]-1] += [e]
s = []
for e in l:
    k = 0
    for i in e:
        s += [[i[0],k+1,i[2]]]
        k += 1
s.sort(key=lambda x: x[2])
for e in s:
    print(str('0'*(6-len(str(e[0]))))+str(e[0])+str('0'*(6-len(str(e[1]))))+str(e[1]))

Solution (Python):
s=input().split()
n,m=int(s[0]),int(s[1])
l=[[] for i in range(100001)]
d=[{} for i in range(100001)]
input_memo=[]
for i in range(m):
    s=input().split()
    p,y=int(s[0]),int(s[1])
    input_memo.append((p,y))
    l[p].append(y)
for i in range(100001):
    l[i].sort()
for i in range(100001):
    cnt=1
    for j in l[i]:
        d[i][j]=cnt
        cnt+=1
for (p,y) in input_memo:
    print(str(p).zfill(6)+str(d[p][y]).zfill(6))

Solution (Python):
s=input().split()
n,m=int(s[0]),int(s[1])
l=[[] for i in range(100001)]
d=[{} for i in range(100001)]
inp=[]
for i in range(m):
    s=input().split()
    p,y=int(s[0]),int(s[1])
    inp.append((p,y))
    l[p].append(y)
for i in range(100001):
    l[i].sort()
for i in range(100001):
    cnt=1
    for j in l[i]:
        d[i][j]=cnt
        cnt+=1
for pa in inp:
    print(str(pa[0]).zfill(6)+str(d[pa[0]][pa[1]]).zfill(6))

Solution (Python):
from itertools import groupby

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

py = [py_i + [i] for i, py_i in enumerate(py)]
py_ = []
for key, group in groupby(sorted(py, key=lambda x: x[0]), lambda x: x[0]):
	for i, city in enumerate(sorted(group, key=lambda x: x[1])):
		py_.append(city + [i+1])

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

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

Solution (Python):


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

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

pyx.sort(key=lambda x:x[2])
pcount = [1 for i in range(n+1)]

for i in pyx:

    i.append(pcount[i[1]])
    pcount[i[1]] += 1


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

for i in pyx:
    print("{:0=6}{:0=6}".format(i[1], i[3]))

Solution (Python):
N, M = map(int, input().split())
cnt = [0 for i in range(N + 1)] 
check = []
ans = []

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

check.sort()

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

ans.sort()

for aa, bb in ans:
    print(bb)

Solution (Python):
from operator import itemgetter

N,M=map(int,input().split())
PY=[]
P=[[] for i in range(N)]
ans=[0 for i in range(M)]
for i in range(M):
    PYi=list(map(int,input().split()))
    PY.append(PYi)
    P[PYi[0]-1].append([i,PYi[1]])

for i in range(N):
    P[i]=sorted(P[i], key=itemgetter(1))

for i in range(N):
    for j in range(len(P[i])):
        ans[P[i][j][0]]=j+1

for i in range(M):
    a=format(PY[i][0],'06d')
    b=format(ans[i],'06d')
    print(a+b)

Solution (Python):
I=lambda:list(map(int,input().split()))[::-1];m,n=I();l=[I()+[i]for i in range(m)];c=[0]*-~n;a=[0]*m
for y,p,i in sorted(l):c[p]+=1;a[i]='%06d'%p+'%06d'%c[p]
print('\n'.join(a))

Solution (Python):
I=lambda:list(map(int,input().split()));n,m=I();l=[I()[::-1]+[i]for i in range(m)];c=[0]*-~n;a=[0]*m
for y,p,i in sorted(l):c[p]+=1;a[i]='%06d'%p+'%06d'%c[p]
for t in a:print(t)

Solution (Python):
I=lambda:list(map(int,input().split()));n,m=I();l=[I()+[i]for i in range(m)];c=[0]*-~n;a=[0]*m
for p,y,i in sorted(l,key=lambda x:x[1]):c[p]+=1;a[i]='%06d'%p+'%06d'%c[p]
for t in a:print(t)

Solution (Python):
import numpy as np

n, m = list(map(int, input().split()))
mat = np.zeros((m, 3))
for i in range(m):
	mat[i, 0], mat[i, 1] = list(map(int, input().split()))
	mat[i, 2] = i
mat = mat[mat[:, 1].argsort()]
cnt = np.zeros(n+1)
res = []
for i in mat[:, 0]:
	i = int(i)
	cnt[i-1] += 1
	res.append('{0:06d}{1:06d}'.format(i, int(cnt[i-1])))

for idx in np.argsort(mat[:, 2]):
	print(res[int(idx)])

Solution (Python):
I=lambda:map(int,input().split());n,m=I();l=[[]for _ in[0]*-~n];a=[]
for i in range(m):p,y=I();l[p].append([y,i])
for p in range(1,n+1):
 for i,t in enumerate(sorted(l[p])):a.append([t[1],'%06d'%p+'%06d'%-~i])
for t in sorted(a):print(t[1])

Solution (Python):
N,M=map(int,input().split())
table=[]
for i in range(M):
    p,y=map(int,input().split())
    table.append((p,y,i))
table.sort()
L=[[0]*2 for i in range(M)]
s=0
t=0
for p,y,i in table:
    if s!=p:
        s=p
        t=1
    else:
        t+=1
    L[i][0]=s
    L[i][1]=t
for i in range(M):
    print('%06d'%L[i][0]+'%06d'%L[i][1])

Solution (Python):
I=lambda:map(int,input().split())
n,m=I()
l=[[]for _ in range(n+1)]
for i in range(m):
  p,y=I()
  l[p].append([y,i])
a=[]
for p in range(1,n+1):
  l[p].sort()
  for i,t in enumerate(l[p]):
    a.append([t[1],'%06d'%p+'%06d'%-~i])
a.sort()
for t in a:
  print(t[1])

Solution (Python):
I=lambda:map(int,input().split())
n,m=I()
l=[[]for _ in range(n+1)]
for i in range(m):
  p,y=I()
  l[p].append([y,i])
a=[]
for p in range(1,n+1):
  l[p].sort()
  for i,t in enumerate(l[p]):
    a.append([t[1],'%06d'%p+'%06d'%-~i])
a.sort()
for t in a:
  print(t[1])

Solution (Python):

import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    def addCity(d,p,m,i):
        if p in d:
            d[p].append((m,i))
        else:
            d[p]=[(m,i)]
    dC = {}
    for i in range(iM):
        p,m = (int(_) for _ in sys.stdin.readline().split())
        addCity(dC,p,m,i)
    oAns = []
    for iCity in dC.keys():
        iIndex = 1
        for m,originIndex in sorted(dC[iCity]):
            oAns.append((originIndex,'{:06}{:06}'.format(iCity,iIndex)))
            iIndex += 1
    oAns.sort()
    print("\n".join(map(lambda x:x[1] ,oAns)))
解()

Solution (Python):

import sys

def 解():
    iN,iM = [int(_) for _ in input().split()]
    def addCity(d,p,m,i):
        if p in d:
            d[p].append((m,i))
        else:
            d[p]=[(m,i)]
    dC = {}
    iIndex = 1
    for p,m in [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]:
        addCity(dC,p,m,iIndex)
        iIndex += 1
    oAns = []
    for iCity in dC.keys():
        iIndex = 1
        for m,i in sorted(dC[iCity]):
            oAns.append((i,'{:06}{:06}'.format(iCity,iIndex)))
            iIndex += 1
    oAns.sort()
    print("\n".join(map(lambda x:x[1] ,oAns)))
解()

Solution (Python):
N, M = [int(s) for s in input().rstrip().split()]
pref = [[] for _ in range(N)]
P = []
for m in range(M):
    p, year = [int(s) for s in input().rstrip().split()]
    pref[p-1].append([year, m])
    P.append(p)

id = [None] * M
for n, p in enumerate(pref):
    if not p:
        continue    
    p.sort()
    for x, (year, m) in enumerate(p):
        id[m] = '{0:06d}{1:06d}'.format(n+1, x+1)

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

Solution (Python):
N, M = map(int, input().split(" "))
cityList = []


class City:
    def __init__(self, id, pre, year):
        self.id = id
        self.pre = pre
        self.year = year
        self.number = ""


for i in range(M):
    P, Y = map(int, input().split(" "))
    city = City(i + 1, P, Y)
    cityList.append(city)

cityList.sort(key=lambda x: x.year)
cityList.sort(key=lambda x: x.pre)

num = 0
count = 0
for city in cityList:
    if city.pre != num:
        num = city.pre
        count = 1
    city.number = str(num).zfill(6) + str(count).zfill(6)
    count += 1

cityList.sort(key=lambda x: x.id)
for city in cityList:
    print(city.number)

Solution (Python):
"""
import numpy as np
N, M = map(int, input().split())
cities = {}
Y = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = p
    Y[i] = y

ans = {}
sorted_Y = sorted(Y.items(), key=lambda x:x[1])
P_i = np.zeros(N)
for i,y in sorted_Y:
    p = cities[i]
    P_i[p-1] += 1
    ans[i] = (p, int(P_i[p-1]))

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

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

pys.sort()
pp = -1
lid = 0
ans = [0]*m
for i in range(m):
    if pp == pys[i][0]:
        lid += 1
    else:
        lid = 1
        pp = pys[i][0]
    ans[pys[i][2]] = pp*10**6+lid

for v in ans:
    print('{:012d}'.format(v))

Solution (Python):
n, m = map(int, input().split())
a = [0] * (n+1)
b = [list(map(int, input().split())) + [i] + [0] for i in range(m)]
b.sort(key= lambda x:x[1])
for i, (v, x, y, z) in enumerate(b):
    a[v-1] += 1
    b[i][3] = a[v-1]
b.sort(key = lambda x:x[2])
for v,x,y,z in b:
    print("{0:06d}{1:06d}".format(v,z))

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

num = [0]*N
ans = [""]*M

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

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

for a in ans:
    print(a)

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

a,b = map(int,input().split())
aa = []
d = []
for i in range(b):
    k,kk = map(int,input().split())
    d.append([k, kk,i+1])

da = sorted(d)

kkk = da[0][0]
ll = 0
for i in range(b):
    kkkk = da[i][0]
    if kkk == kkkk:
        ll += 1
    else:
        kkk = kkkk
        ll = 1
    aa.append([da[i][2],da[i][0],ll])
aa.sort()

for i in aa:
    m = str(i[1])
    n = str(i[2])
    m = "0"*(6-len(m))+m
    n = "0"*(6-len(n))+n
    print(m+n)