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


def main():
    N, M =  [int(i) for i in input().split()]
    cities = []

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

    cities.sort()
    ans = []

    num = 0
    before = cities[0][0]

    for i in range(M):
        if before != cities[i][0]:
            num = 1
            before = cities[i][0]
        else:
            num += 1
        ans.append([cities[i][0], num, cities[i][2]])

    ans.sort(key=lambda x:x[2])
    for a in ans:
        s = str(a[0]).zfill(6) + str(a[1]).zfill(6)
        print(s)



if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    answer = ["" for _ in range(m)]
    all_pref = {}
    for i in range(m):
        p, y = map(int, input().split())
        if p in all_pref:
            all_pref[p].append([y, i])
        else:
            all_pref[p] = [[y, i]]
    for pref, date in all_pref.items():
        date.sort(key=lambda x: x[0])
        order = 0
        for year, num in date:
            answer[num] = str(pref).zfill(6) + str(order + 1).zfill(6)
            order += 1
    print("\n".join(answer))


if __name__ == '__main__':
    main()

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

    
xx = [[] for _ in range(m)]
for ken in range(0, n):
    py[ken].sort(key=lambda x: x[0])
    for i in range(len(py[ken])):
        x = py[ken][i]
        xx[x[1]] = "%s%s" % (str(ken+1).zfill(6), str(i+1).zfill(6))
print("\n".join(xx), end="")

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

PY.sort()

ans = [None for i in range(M)]

x = 1
P = PY[0][0]
for i in range(M):
    if P != PY[i][0]:
        x = 1
        P = PY[i][0]

    ans[PY[i][2]] = (P,x)
    x += 1

for p,x in ans:
    print(str(p).zfill(6) + str(x).zfill(6))

Solution (Python):
def pad(n):
	n = str(n)
	if len(n) < 6:
		n = "0"*(6-len(n))+n
	return n

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

for i in range(M):
	PY[i].append(i)
PY.sort()

turn = 1
PY[0].append(pad(PY[0][0])+pad(turn))
for i in range(1,M):
	if PY[i][0] != PY[i-1][0]:
		turn = 1
	else:
		turn += 1
	PY[i].append(pad(PY[i][0])+pad(turn))

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

Solution (Python):


nim,mike=map(int,input().split())

array=[]

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

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

k=list(range(1,10**5+1))

v=[0]*10**5

cnt_dict=dict(zip(k,v))

arr=[]

for i,j,k in PY_sort:
    cnt_dict[j]+=1
    arr.append([i,str(j).zfill(6)+str(cnt_dict[j]).zfill(6)])

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

for a,b in s:
    print(b)

Solution (Python):

















mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,m = readInts()
    from collections import defaultdict
    import bisect
    p = [list(map(int,input().split())) for _ in range(m)]
    a = defaultdict(list)
    for x,y in sorted(p):
        a[x] += [y]
    for x,y in p:
        z = bisect.bisect_right(a[x],y)
        print("%06d%06d"%(x,z))
if __name__ == '__main__':
  main()

Solution (Python):


def solve():
    N, M = map(int, input().split())

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

    ans = [None]*M
    
    
    for p, iys in enumerate(piys):
        iys.sort()
        
        
        for k, (y, i) in enumerate(iys):
            pref = str(p+1)
            born = str(k+1)
            
            ans[i] = pref.rjust(6, "0")+born.rjust(6, "0")

    for i in ans:
        print(i)


if __name__ == "__main__":
    solve()

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

Solution (Python):
import sys
import math  
import bisect  
import queue  


if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().rstrip().split())
    PY = []
    for i in range(M):
        P, Y = map(int, sys.stdin.readline().rstrip().split())
        PY.append([Y, P, i + 1])
    PY.sort()

    
    
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])

    res.sort()
    for i, p, x in res:
        print('{:06}{:06}'.format(p, x))

Solution (Python):
import sys
import math  
import bisect  
import queue  


if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().rstrip().split())
    PY = []
    for i in range(M):
        P, Y = map(int, sys.stdin.readline().rstrip().split())
        PY.append([Y, P, i + 1])
    PY.sort()

    
    
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])

    res.sort()
    for i, p, x in res:
        print('{:06}{:06}'.format(p, x))

Solution (Python):
import sys
import math  
import bisect  
import queue  


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


if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = []
    for i in range(M):
        P, Y = map(int, input().split())
        PY.append([Y, P, i + 1])
    PY.sort()

    
    
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])

    res.sort()
    for i, p, x in res:
        print('{:06}{:06}'.format(p, x))

Solution (Python):
import sys
import math  
import bisect  
import queue  


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


if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = []
    for i in range(M):
        P, Y = map(int, input().split())
        PY.append([Y, P, i + 1])
    PY.sort()

    
    
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])

    res.sort()
    for i, p, x in res:
        print('{:06}{:06}'.format(p, x))

Solution (Python):
import math  
import bisect  
import queue  


if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = []
    for i in range(M):
        P, Y = map(int, input().split())
        PY.append([Y, P, i + 1])
    PY.sort()

    
    
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])

    res.sort()
    for i, p, x in res:
        print('{:06}{:06}'.format(p, x))

Solution (Python):
import math  
import bisect  
import queue  


if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = []
    for i in range(M):
        P, Y = map(int, input().split())
        PY.append([Y, P, i + 1])
    PY.sort()

    
    
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])

    res.sort()
    for i, p, x in res:
        print('{:06}{:06}'.format(p, x))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    return


def B():
    return


def C():
    n, m = LI()
    py = LIR(m)
    pya = py[::1]
    py.sort(key=lambda x: x[1])
    city = [1 for i in range(n)]
    dicity = {}
    for p, y in py:
        dicity[(p,y)] = city[p-1]
        city[p-1] += 1    
    for p, y in pya:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(dicity[(p, y)])
        b = b[-6:]
        print(a+b)

    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    C()

Solution (Python):

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


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

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

ans = [0] * m
for i in range(n):
    cities = prefec[i]
    cities.sort(key=lambda x: x[0])
    for j in range(len(cities)):
        _, index = cities[j]
        p = i + 1
        num = j + 1
        ans[index] = '0' * (6 - len(str(p))) + str(p) + '0' * (6 - len(str(num))) + str(num)

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

Solution (Python):
from collections import Counter
N, M = list(map(int,input().split()))
city_list = [list(map(int,input().split())) +[i+1]  for i in range(M)]
city_list_sorted = sorted(city_list,key=lambda x: (x[0],x[1]) )
pre = 0
counter = 0

for i in range(M):
  if pre == city_list_sorted[i][0]:
    counter+=1
    city_list_sorted[i][1] = counter
  else:
    counter = 1
    city_list_sorted[i][1] = counter
    pre = city_list_sorted[i][0]

anslist = [[x[2]]+[format(x[0],'0>6') + format(x[1],'0>6') ] for x in city_list_sorted]
[print(x[1]) for x in sorted(anslist)]

Solution (Python):
n,m = map(int,input().split())
ken = [[] for i in range(n)]
jun = [0] * m
p = [0] * m
for i in range(m):
    p[i],y = map(int,input().split())
    ken[p[i]-1].append((y,i))
    
for i in range(n):
    if ken[i] == []:
        continue
    else:
        ken[i].sort()
        for j in range(len(ken[i])):
            jun[ken[i][j][1]] = j+1
            
for i in range(m):
    jun[i] += p[i] * 1000000
    ss = str(jun[i])
    s = "0"*(12-len(ss)) + ss
    print(s)

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


def binary_search(l, item):
    left = 0
    right = len(l) - 1
    while left <= right:
        mid  = (left + right) // 2
        if l[mid] == item:
            return mid
        elif l[mid] < item:
            left = mid + 1
        else:
            right = mid - 1
    return -1
for i in range(m):
    p,y = keys_ls[i]
    rank = binary_search(pref_ls[p], y)
    ans = str(p).zfill(6) + str(rank).zfill(6)
    print(ans)

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 i in range(n):
    pyi[i].sort()
    for j in range(len(pyi[i])):
        ans.append([(6-len(str(i+1)))*"0"+str(i+1)+(6-len(str(j+1)))*"0"+str(j+1),pyi[i][j][1]])
ans.sort(key=lambda x:x[1])
for i in range(m):
    print(ans[i][0])

Solution (Python):
n,m=map(int,input().split())
C=[]
for i in range(m):
    p,y=map(int,input().split())
    C.append([p,y,i])
C.sort()
A=[""]*m
nowP=0
nowX=0
for c in C:
    p=c[0]
    y=c[1]
    i=c[2]
    if p==nowP:
        nowX+=1
        lenX=len(str(nowX))
        A[i]="0"*(6-lenP)+str(nowP)+"0"*(6-lenX)+str(nowX)
    else:
        nowP=p
        lenP=len(str(nowP))
        nowX=1
        lenX=1
        A[i]="0"*(6-lenP)+str(nowP)+"0"*(6-lenX)+str(nowX)
print(*A,sep="\n")

Solution (Python):
n,m = map(int,input().split())
py = []
p_y = [[] for i in range(n)]
for _ in range(m):
    p,y = map(int,input().split())
    py.append((p,y))
    p_y[p-1].append(y)
ans = {}
for i, tmp in enumerate(p_y):
    cnt = 1
    p_y[i] = tmp.sort()
    for j, jj in enumerate(tmp):

        ans[(i+1, jj)] = str(i+1).zfill(6) + str(j+1).zfill(6)


for i, tmp in enumerate(py):
    print(ans[tmp])

Solution (Python):
n,m = map(int,input().split())
py = []
p_y = [[] for i in range(n)]
for _ in range(m):
    p,y = map(int,input().split())
    py.append((p,y))
    p_y[p-1].append(y)
ans = {}
for i, tmp in enumerate(p_y):
    cnt = 1
    p_y[i] = tmp.sort()
    for j, jj in enumerate(tmp):

        ans[(i+1, jj)] = str(i+1).zfill(6) + str(j+1).zfill(6)


for i, tmp in enumerate(py):
    print(ans[tmp])

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

A = []
for i in range(M):
  A.append([i,1000000000000])

for i in range(M):
  PY[i].extend(A[i])

PY.sort()

P = 0


for i in range(M):
  if P != PY[i][0]:
    P = PY[i][0]
    S = 1

  else:
    S += 1

  PY[i][3] += PY[i][0]*1000000+S

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

for i in range(M):
  ans = str(PY[i][3])
  print(ans[1:])

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]))
cnt = 1
ans = [""]*m
for i in range(m-1):
  ans[py[i][2]] = "0"*(6-len(str(py[i][0])))+str(py[i][0]) + "0"*(6-len(str(cnt)))+str(cnt)
  if py[i][0] == py[i+1][0]:
    cnt += 1
  else:
    cnt = 1
ans[py[m-1][2]]="0"*(6-len(str(py[m-1][0])))+str(py[m-1][0]) + "0"*(6-len(str(cnt)))+str(cnt)
for i in range(m):
  print(ans[i])

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

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

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

p = cities[0][0]
cnt = 1
for i in range(M):

    if (cities[i][0] == p):
        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6))
        cnt += 1
    else:
        p = cities[i][0]
        cnt = 1
        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6))
        cnt += 1

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

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

Solution (Python):
N, M = map(int, input().split())
pref = [[] for _ in range(N)]
P,Y = [0]*M,[0]*M
for i in range(M):
    P[i],Y[i] = map(int, input().split())
    pref[P[i]-1].append(Y[i])

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

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

def solve(P,Y,pref):
    ans = []
    for p, y in zip(P,Y):
        ind = bisect_left(pref[p-1],y)+1
        num = '0'*(6-len(str(p)))+str(p)+'0'*(6-len(str(ind)))+str(ind)
        ans.append(num)
    return ans
print(*solve(P,Y,pref),sep='\n')

Solution (Python):
from collections import defaultdict
n, m = map(int, input().split())
l = []
dic = defaultdict(list)
for i in range(m):
    p, y = map(int, input().split())
    dic[p].append(y)
    l.append([p, y])
for key, value in dic.items():
    dic[key] = {num: index+1 for index,num in enumerate(sorted(value))}
for p, y in l:
    print(str(p).zfill(6)+str(dic[p][y]).zfill(6))

Solution (Python):
def I(): return map(int, input().split())
n, m = I()
d = []
for _ in range(m):
    d += [list(I())]
u = sorted([[i, j] for i, j in enumerate(d)], key=lambda x: x[1])

f = 0
r = 0 
for _, j in u:
    p, _ = j
    if f != p:
        x = 1
    u[r][1] = [str(p).zfill(6) + str(x).zfill(6)]
    x += 1
    f = p
    r += 1

for _, k in sorted(u):
    print(*k)

Solution (Python):
from collections import defaultdict


def create_id(p, o):
    return str(p).zfill(6) + str(o).zfill(6)


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

ans = [None] * m
for p in db:
    db[p].sort()
    for i in range(len(db[p])):
        ans[db[p][i][1]] = create_id(p, i + 1)
print(*ans, sep="\n")

Solution (Python):

from bisect import bisect_right
import sys

readline = sys.stdin.readline
n, m = map(int, readline().split())
ken = [list() for _ in range(n)]
PY = []
for _ in range(m):
    p, y = map(int, readline().split())
    PY.append((p, y))
    ken[p-1].append(y)
for i in range(n):
    ken[i].sort()

for p, y in PY:
    print(str(p).zfill(6) + str(bisect_right(ken[p-1],y)).zfill(6))

Solution (Python):
import sys

def fill(s): return '0' * (6 - len(s)) + s
def create_id(p, o): return fill(str(p)) + fill(str(o))

n, m, *py = map(int, sys.stdin.read().split())
pyi = sorted(zip(*[iter(py)] * 2 + [range(m)]))

def main():
    res = [None] * m
    prev = j = None
    for p, y, i in pyi:
        j = j + 1 if p == prev else 1
        res[i] = create_id(p, j)
        prev = p
    print(*res, sep='\n')
    
if __name__ ==  '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

def fill(s):
    while len(s) < 6: s = '0' + s
    return s

def create_id(p, o):
    return fill(str(p)) + fill(str(o))

n, m, *py = map(int, sys.stdin.read().split())
py = zip(*[iter(py)] * 2)

def main():
    db = defaultdict(list)
    i = 0
    for p, y in py:
        db[p].append((y, i))
        i += 1

    res = [None] * m
    for p in db:
        db[p].sort()
        for i in range(len(db[p])):
            res[db[p][i][1]] = create_id(p, i + 1)
    print(*res, sep='\n')

if __name__ ==  '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

def create_id(p, o):
    p = str(p)
    o = str(o)
    p = '0' * (6 - len(p)) + p
    o = '0' * (6 - len(o)) + o
    return p + o

n, m, *py = map(int, sys.stdin.read().split())
py = zip(*[iter(py)] * 2)

def main():
    db = defaultdict(list)
    i = 0
    for p, y in py:
        db[p].append((y, i))
        i += 1

    res = [None] * m
    for p in db:
        db[p].sort()
        for i in range(len(db[p])):
            res[db[p][i][1]] = create_id(p, i + 1)
    print(*res, sep='\n')

if __name__ ==  '__main__':
    main()

Solution (Python):





mod = 10**9 + 7

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



if __name__ == '__main__':
  main()

Solution (Python):
a,b = map(int,input().split())
py = sorted([list(map(int,input().split()))+[i] for i in range(b)])
c = 1
ans1 = [['0'*(6 - len(str(py[0][0])))+str(py[0][0])+'000001',py[0][2]]]
for i in range(1,b):
  ans = '0'*(6 - len(str(py[i][0])))
  ans += str(py[i][0])
  if py[i-1][0] == py[i][0]:
    c += 1
  else:
    c = 1
  ans += '0'*(6 - len(str(c)))
  ans += str(c)
  ans1.append([ans,py[i][2]])
ans1 = sorted(ans1,key=lambda x:x[1])
for i in ans1:
  print(i[0])

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

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


ans = []
last_p = -1
index = 1
for i in range(m):
  p,y,j = array[i]
  
  if p != last_p:
    index = 1
    
  number = str(p).zfill(6) + str(index).zfill(6)
  ans.append((j,number))
  
  last_p = p
  index += 1
  
for t in sorted(ans):
  print(t[1])

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

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

pref = [[] for _ in range(N)]

res = []

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

for ar in pref:
    ar.sort()

for pre, year in res:
    p = str(pre + 1)
    p_zero = p.zfill(6)
    y = str(bisect.bisect_left(pref[pre], year) + 1)
    y_zero = y.zfill(6)
    print(p_zero + y_zero)

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
P, Y = [], []
ylist = defaultdict(list)
pset = set()
for i in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)
    ylist[p].append(y)
    pset.add(p)

cdict = defaultdict(dict)
for p in pset:
    syear = sorted(ylist[p])
    for i, y in enumerate(syear):
        cdict[p][y] = i + 1

for i in range(M):
    p = P[i]
    y = Y[i]
    rank = cdict[p][y]
    print('{:06}{:06}'.format(p, rank))

Solution (Python):
N,M=map(int,input().split())
shi=[[] for i in range(N+1)]
py=[]
for i in range(M):
    p,y=map(int,input().split())
    shi[p].append(y)
    py.append([p,y])
for i in range(N+1):
    shi[i].sort()
shidic=[{} for i in range(N+1)]
for i in range(N+1):
    for j in range(len(shi[i])):
        shidic[i][shi[i][j]]=j+1
for P,Y in py:
    print(str(P).zfill(6)+str(shidic[P][Y]).zfill(6))

Solution (Python):
n,m = map(int,input().split())
a = [[] for _ in range(n)]
for i in range(1,m+1):
  pi,yi = map(int,input().split())
  a[pi-1].append((yi,i))
ans = [0 for _ in range(m)]
for i in range(n):
  if a[i]:
    a[i].sort(key=lambda x:x[0])
    c = (i+1)*10**6
    for j in range(len(a[i])):
      ans[a[i][j][1]-1] = c + j+1
for xx in ans:
  xs = str(xx)
  xs = "0"*(12-len(xs)) + xs
  print(xs)

Solution (Python):
n, m = map(int, input().split())
dic = {}
ans = [0]*m
for i in range(m):
  p, y = map(int, input().split())
  dic.setdefault(p, []).append([y, i])
for i, j in dic.items():
  j = sorted(j)
  for k, l in enumerate(j):
    ans[l[1]]= str(i).zfill(6) + str(k + 1).zfill(6)
for i in range(len(ans)):
  print(ans[i])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect 


def main():
    N, M = mi()
    l = dp2(0, 3, M)
    for i in range(M):
        p, x = mi()
        l[i][0], l[i][1], l[i][2] = p, x, i 
    l.sort(key=lambda x :(x[0], x[1]))

    ans = ['' for _ in range(M)]
    cnt = 0
    bf = 1
    for i in range(M):
        a = l[i][0]
        if a > bf:
            cnt = i
        b, c = str(i+1-cnt), l[i][2]
        ans[c] = str(a).zfill(6) + b.zfill(6)
        bf = a

    
    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect 


def ume(x):
    x = str(x)
    if len(x) < 6:
        return '0'*(6-len(x)) + x
    return x

def main():
    N, M = mi()
    '''
    l = dp2(0, 3, M)
    cnt = [0]*(N+1)
    ans = dp2(0, 2, M)
    for i in range(M):
        p, y = mi()
        l[i][0], l[i][1], l[i][2] = p-1, y, i
        cnt[p] += 1
    for i in range(N):
        cnt[i+1] += cnt[i]

    l.sort(key=lambda x: x[0])
    for i in range(N):
        ichibu = l[cnt[i]:cnt[i+1]]
        ichibu.sort(key=lambda x: x[1])
        for j in range(cnt[i+1]-cnt[i]):
            ans[ichibu[j][2]][0] = ichibu[j][0]+1
            ans[ichibu[j][2]][1] = j+1
    
    for x, y in ans:
        print(ume(x)+ume(y))
    '''

    l = li2(M)
    pos = [[] for _ in range(N+1)]
    ans = dp2(0, 2, M)

    for a, b in l:
        pos[a].append(b)
    for a in pos:
        a.sort()
    for i, a in enumerate(l):
        ind = bisect.bisect_left(pos[a[0]], a[1])
        l[i][1] = ind+1
        print(ume(l[i][0])+ume(l[i][1]))





if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect 


def ume(x):
    x = str(x)
    if len(x) < 6:
        return '0'*(6-len(x)) + x
    return x

def main():
    N, M = mi()
    '''
    l = dp2(0, 3, M)
    cnt = [0]*(N+1)
    ans = dp2(0, 2, M)
    for i in range(M):
        p, y = mi()
        l[i][0], l[i][1], l[i][2] = p-1, y, i
        cnt[p] += 1
    for i in range(N):
        cnt[i+1] += cnt[i]

    l.sort(key=lambda x: x[0])
    for i in range(N):
        ichibu = l[cnt[i]:cnt[i+1]]
        ichibu.sort(key=lambda x: x[1])
        for j in range(cnt[i+1]-cnt[i]):
            ans[ichibu[j][2]][0] = ichibu[j][0]+1
            ans[ichibu[j][2]][1] = j+1
    
    for x, y in ans:
        print(ume(x)+ume(y))
    '''

    l = li2(M)
    pos = [[] for _ in range(N+1)]
    ans = dp2(0, 2, M)

    for a, b in l:
        pos[a].append(b)
    for a in pos:
        a.sort()
    for i, a in enumerate(l):
        ind = bisect.bisect_left(pos[a[0]], a[1])
        l[i][1] = ind+1
        print(ume(l[i][0])+ume(l[i][1]))

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]



def ume(x):
    x = str(x)
    if len(x) < 6:
        return '0'*(6-len(x)) + x
    return x

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

    l = dp2(0, 3, M)
    cnt = [0]*(N+1)
    ans = dp2(0, 2, M)
    for i in range(M):
        p, y = mi()
        l[i][0], l[i][1], l[i][2] = p-1, y, i
        cnt[p] += 1
    for i in range(N):
        cnt[i+1] += cnt[i]

    l.sort(key=lambda x: x[0])
    for i in range(N):
        ichibu = l[cnt[i]:cnt[i+1]]
        ichibu.sort(key=lambda x: x[1])
        for j in range(cnt[i+1]-cnt[i]):
            ans[ichibu[j][2]][0] =ichibu[j][0]+1
            ans[ichibu[j][2]][1] =j+1
    
    for x, y in ans:
        print(ume(x)+ume(y))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]



def ume(x):
    x = str(x)
    if len(x) < 6:
        return '0'*(6-len(x)) + x
    return x

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

    l = dp2(0, 3, M)
    cnt = [0]*(N+1)
    ans = dp2(0, 2, M)
    for i in range(M):
        p, y = mi()
        l[i][0], l[i][1], l[i][2] = p-1, y, i
        cnt[p] += 1
    for i in range(N):
        cnt[i+1] += cnt[i]

    l.sort(key=lambda x: x[0])
    for i in range(N):
        ichibu = l[cnt[i]:cnt[i+1]]
        ichibu.sort(key=lambda x: x[1])
        for j in range(cnt[i+1]-cnt[i]):
            ans[ichibu[j][2]][0] =ichibu[j][0]+1
            ans[ichibu[j][2]][1] =j+1
    
    for x, y in ans:
        print(ume(x)+ume(y))


if __name__ == "__main__":
    main()

Solution (Python):
import bisect as bis
n, m = map(int, input().split())
p, y = [], []
idx = lambda x: x-1
for _ in range(m):
    p_, y_ = map(int, input().split())
    p.append(p_)
    y.append(y_)
val = [[] for _ in range(n)]
for i in range(m):
    val[idx(p[i])].append(y[i]) 
for i in range(n):  
    val[i].sort()
for i in range(m):
    v = p[i]
    id = bis.bisect_right(val[idx(v)], y[i])  
    print(str(v).zfill(6) + str(id).zfill(6))

Solution (Python):
N, M = map(int, input().split())
p = []
for i in range(M):
    tmp = list(map(int, input().split()))
    tmp.append(i)
    p.append(tmp)
p.sort()
ans = []
count = 1
for i in range(M):
    if p[i-1][0] != p[i][0]:
        count = 1
    elif i != 0:
        count += 1
    id = str(p[i][0]).zfill(6)+str(count).zfill(6)
    ans.append((p[i][2],id))
ans.sort()
for i in ans:
    print(i[1])

Solution (Python):
N, M = map(int, input().split())
pref = [1] * (N + 1)
iPY = []
for i in range(M):
    p, y = map(int, input().split())
    iPY.append([i, p, y])

iPY.sort(key=lambda x: x[2])
ans = []
for i, p, y in iPY:
    name = str(p).zfill(6) + str(pref[p]).zfill(6)
    ans.append((i, name))
    pref[p] += 1

ans.sort(key=lambda x: x[0])
for _, name in ans:
    print(name)

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

def kansu(N,M,S):

    S_tmp=[]
    for i in range(M):
        tmp = [int(S[i][0]),int(S[i][1]),0,i]
        S_tmp.append(tmp) 
    S_tmp.sort()
    tmp = S_tmp[0][0]
    cnt = 1

    for i in range(M):
        if tmp == int(S_tmp[i][0]):
            S_tmp[i][2] = cnt
            cnt += 1
        else :
            tmp = S_tmp[i][0]
            S_tmp[i][2] = 1
            cnt = 2

    S_tmp = sorted(S_tmp, key=lambda x: x[3])

    for i in range(M):
        print(str(S_tmp[i][0]).zfill(6),str(S_tmp[i][2]).zfill(6),sep='')
    



    
    
    
    
    
    
    
    


N,M,S = nyu()
kansu(N,M,S)