Problem:
 Score: 300 points    Problem Statement In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to those prefectures.  City i is established in year Y_i and belongs to Prefecture P_i .  You can assume that there are no multiple cities that are established in the same year.  It is decided to allocate a 12 -digit ID number to each city.  If City i is the x -th established city among the cities that belong to Prefecture i , the first six digits of the ID number of City i is P_i , and the last six digits of the ID number is x .  Here, if P_i or x (or both) has less than six digits, zeros are added to the left until it has six digits.  Find the ID numbers for all the cities.  Note that there can be a prefecture with no cities.      Constraints  1 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq P_i \leq N  1 \leq Y_i \leq 10^9  Y_i are all different.  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  P_1  Y_1  :  P_M  Y_M       Output Print the ID numbers for all the cities, in ascending order of indices (City 1 , City 2 , ... ).        Sample Input 1 2 3
1 32
2 63
1 12      Sample Output 1 000001000002
000002000001
000001000001   As City 1 is the second established city among the cities that belong to Prefecture 1 , its ID number is 000001000002 .  As City 2 is the first established city among the cities that belong to Prefecture 2 , its ID number is 000002000001 .  As City 3 is the first established city among the cities that belong to Prefecture 1 , its ID number is 000001000001 .        Sample Input 2 2 3
2 55
2 77
2 99      Sample Output 2 000002000001
000002000002
000002000003

Solution (Python):
import math

def A():
    x, a, b = [int(x) for x in input().split()]
    if abs(x-a) < abs(x-b):
        print('A')
    else:
        print('B')
def B():
    S = input()
    alphabet = [False for x in range(26)]
    for char in S:
        i = ord(char) - ord('a')
        alphabet[i] = True
    printed = False
    for i in range(len(alphabet)):
        if alphabet[i] == False:
            print(chr(ord('a')+i))
            printed = True
            break
    if printed == False:
        print("None")
def C():
    pass

def E():
    n, m = [int(x) for x in input().split()]
    P = [[] for i in range(n)]
    for j in range(m):
        p, y = [int(x) for x in input().split()]
        P[p-1].append([y, ('000000'+str(p))[-6:], j])

    for i in range(n):
        P[i] = sorted(P[i], key=lambda x:x[0])
        for j in range(len(P[i])):
            P[i][j][1] += (('000000'+str(j+1))[-6:])
    P = [e for inner_list in P for e in inner_list]
    P = sorted(P, key=lambda x:x[2])
    for p in P:
        print(p[1])
E()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    n,m = LI()
    v = LIR(m)
    for i in range(m):
        v[i] = [v[i][0],v[i][1],i]
    v.sort(key = lambda x:x[1])
    f = [0 for i in range(n+1)]
    ans = [None for i in range(m)]
    for p,y,i in v:
        f[p] += 1
        s = "{:0>6}".format(p)
        t = "{:0>6}".format(f[p])
        ans[i] = s+t
    for i in ans:
        print(i)

def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    C()

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())
p_list = []
for i in range(m):
    p_list.append(list(int(i) for i in input().split()))
a = sorted(p_list)
tmp = 0
b = {}
for (i,j) in a:
    if i != tmp:
        count = 1
        tmp = i
        b[(i,j)] = "0"*(6-len(str(i))) + str(i) + "0"*(6-len(str(count))) + str(count)
    else:
        count += 1
        b[(i,j)] = "0"*(6-len(str(i))) + str(i) + "0"*(6-len(str(count))) + str(count)
for (i,j) in p_list:
    print(b[(i,j)])

Solution (Python):
n,m=[int(i) for i in input().split()]
id=[[int(i) for i in input().split()]+[j] for j in range(m)]
pre_num=[0]*(n+1)
ans=[""]*m
id.sort(key=lambda x:x[1])
for p,y,i in id:
    pre_num[p]+=1
    ans[i]=str(p).zfill(6)+str(pre_num[p]).zfill(6)
print("\n".join(ans))

Solution (Python):
N,M=map(int,input().split())
li=[[list(map(int,input().split())),i] for i in range(M)]
li=sorted(li, key=lambda x:x[0][1])
counter=[0]*N
li_id=[]

for j in li:
    counter[int(j[0][0])-1]+=1
    x=str(j[0][0])
    y=str(counter[int(j[0][0])-1])
    ID=('0'*(6-len(x)))+x+('0'*(6-len(y)))+y
    li_id.append([j[1],ID])
li_id=sorted(li_id)
for k in li_id:
    print(k[1])

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

from operator import itemgetter
I = [0]*(n+1)
Ans = [""]*m

PY.sort(key = itemgetter(1))
for py in PY:
    I[py[0]] += 1
    Ans[py[2]] = str(format(py[0],"06d"))+str(format(I[py[0]],"06d"))
print(*Ans,sep="\n")

Solution (Python):
from sys import exit
N,M = [int(n) for n in input().split()]
P = [0]*M
Y = [0]*M
l = [0]*M
dic = dict(zip(range(1,N+1),[0]*N))
for i in range(M):
    P[i], Y[i] = [int(n) for n in input().split()]
    l[i] = [i,P[i], Y[i], str(P[i]).zfill(6)]

l = sorted(l,key=lambda x:x[2])
for i in range(M):
    dic[l[i][1]]+=1
    l[i][3]+=str(dic[l[i][1]]).zfill(6)
l = sorted(l,key=lambda x:x[0])
for i in range(M):
    print(l[i][3])

Solution (Python):
N, M = map(int, input().split())
anses = [0] * M
pre = [0] * N
 
for idx in range(M):
    p, y = (int(x) for x in input().split())
    anses[idx] = [idx, p, y, 0]

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

for ans in anses:
    pre[ans[1]-1] += 1
    ans[3] = pre[ans[1]-1]

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

for ans in anses:
    print('{:0=6}{:0=6}'.format(ans[1], ans[3]))

Solution (Python):
def main113my():
    N, M = (int(x) for x in input().split())

    answer = [0] * M
    pre = [0] * N

    for m in range(M):
        p, y = (int(x) for x in input().split())
        answer[m] = [m, p, y, 0]

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

    for a in answer:
        pre[a[1]-1] += 1
        a[3] = pre[a[1]-1]

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

    for a in answer:
        print("{:06d}{:06d}".format(a[1], a[3]))

main113my()

Solution (Python):
from operator import itemgetter

N, M = [int(_) for _ in input().split()]
PY = [[__] + [int(_) for _ in input().split()] for __ in range(M)]
PY.sort(key=itemgetter(1, 2))

p = 0
x = 1
for i in PY:
    if p != i[1]:
        p = i[1]
        x = 1
    i.append('{:06}{:06}'.format(p, x))
    x += 1

for i in sorted(PY):
    print(i[3])

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

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

p.sort()
cnt = 0
pre = -1

for city in p:
    if city[0] == pre:
        cnt = cnt + 1
    else:
        pre = city[0]
        cnt = 1

    city.append("{:0>6}{:0>6}".format(city[0], cnt))

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

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

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

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

p = 0
for i in range(M):
    if py[i][0] != p:
        cnt = 1
        p = py[i][0]
    else:
        cnt += 1
    py[i][3] = str(p).zfill(6) + str(cnt).zfill(6)

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

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

PY = sorted(PY, key=lambda x: (x[1], x[2]))
cur = [0 for _ in range(N)]
ans_list = []
for i in range(M):
    ans = '0'*(6-len(str(PY[i][1]))) + str(PY[i][1])
    cur[PY[i][1]-1] += 1
    ans += '0'*(6-len(str(cur[PY[i][1]-1]))) + str(cur[PY[i][1]-1])
    ans_list.append([PY[i][0], ans])

ans_list = sorted(ans_list, key=lambda x: x[0])
for i, v in enumerate(ans_list):
    print(v[1])

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

PY = sorted(PY, key=lambda x: (x[1], x[2]))
cur = [0 for _ in range(N)]
ans_list = []
for i in range(M):
    ans = '0'*(6-len(str(PY[i][1]))) + str(PY[i][1])
    cur[PY[i][1]-1] += 1
    ans += '0'*(6-len(str(cur[PY[i][1]-1]))) + str(cur[PY[i][1]-1])
    ans_list.append([PY[i][0], ans])

ans_list = sorted(ans_list, key=lambda x: x[0])
for i, v in enumerate(ans_list):
    print(v[1])

Solution (Python):
from operator import itemgetter

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

for i in range(M):
  PY.append([i, list(map(int,input().split())), 'x'])

PY.sort(key=itemgetter(1,2))
cnt_pref = {}

for i in range(M):  
  p, y = PY[i][1][0], PY[i][1][1]
  if (p in cnt_pref):
    cnt_pref[p] += 1
  else:
    cnt_pref[p] = 1
  PY[i][2] = str(p).zfill(6) + str(cnt_pref[p]).zfill(6)

PY.sort(key=itemgetter(0))
for i in PY:
  print(i[2])

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

iPYx.sort(key = lambda x: (x[1], x[2]))
cnt = 0
for i in range(M):
  if i == 0 or iPYx[i][1] != iPYx[i - 1][1]:
    cnt = 1
  else:
    cnt += 1
  iPYx[i].append(cnt)
iPYx.sort(key = lambda x: x[0])
for i in range(M):
  print("{:06}{:06}".format(iPYx[i][1], iPYx[i][3]))

Solution (Python):
n, m = [int(item) for item in input().split()]

ids, ps, ys = [], [], []
for i in range(m):
  p, y = [int(item) for item in input().split()]
  ids.append(i)
  ps.append(p)
  ys.append(y)

city_num = [0] * (n+1)
ids, ps, ys = zip(*sorted(zip(ids, ps, ys) ,key = lambda x : x[2]))
names = []

for p in ps:
  city_num[p] += 1
  names.append("{0:06d}".format(p) + "{0:06d}".format(city_num[p]))
  
names, _ = zip(*sorted(zip(names, ids), key=lambda x:x[1]))
for name in names:
  print(name)

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

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

belongs = [0 for _ in range(N)]

for i, (p, y, n) in enumerate(city):
    belongs[p-1] += 1
    city[i].append(belongs[p-1])
    
city = sorted(city, key=lambda x: x[2])

for p, y, n, n_city in city:
    print('{:06d}{:06d}'.format(p, n_city))

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

city_dict = {}
for i, city in enumerate(cities):
    if not city[0] in city_dict:
        city_dict[city[0]] = []
    city_dict[city[0]].append([i, city[1], ""])

ans = []
for key, value in city_dict.items():
    value.sort(key=lambda x: x[1])
    for i, v in enumerate(value):
        v[2] = "{}{}".format(str(key).zfill(6), str(i+1).zfill(6))
    ans.extend(value)
ans.sort(key=lambda x:x[0])
for a in ans:
    print(a[2])

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

appear = [1]*(n+1)
for i in range(m):
    pysorted[i].append(str(pysorted[i][0]).zfill(6) + str(appear[pysorted[i][0]]).zfill(6))
    appear[pysorted[i][0]] += 1
pyresorted = sorted(py,key=lambda x:x[2])
for i in range(m):
    print(py[i][3])

Solution (Python):
N,M=map(int,input().split())
a=[]
for i in range(M):
    n,m=map(int,(input().split()))
    a.append([n,m,i])
ans=['0']*M
a.sort()
j=0
for i in range(M):
    if j!=a[i][0]:
        j=a[i][0]
        c=1
    ans[a[i][2]]=str(a[i][0]).zfill(6)+str(c).zfill(6)
    c+=1
for i in range(M):
    print(ans[i])

Solution (Python):
N,M = map(int,input().split())
PY=[list(map(int,input().split()))+[0] for _ in range(M)]
sort_PY=sorted(PY,key=lambda x:x[1])
c={}
for i in range(M):
    p=sort_PY[i][0]
    if(p in c):
        c[p]+=1
    else:
        c[p]=1
    sort_PY[i][2]=c[p]
for p,y,z in PY:
    print(str(p).zfill(6)+str(z).zfill(6))

Solution (Python):
from collections import defaultdict
def inpl(): return list(map(int,input().split()))

class increment:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

ui = defaultdict(increment())
plist = []
clists = []
Np = 0

N, M = inpl()
P = [0]*M
Y = [0]*M
for i in range(M):
    P[i], Y[i] = inpl()
    p = ui[P[i]]
    if p >= Np:
        plist.append(P[i])
        clists.append([[i,Y[i]]])
        Np += 1
    else:
        clists[p].append([i,Y[i]])

ids = ['']*M
for p in range(Np):
    clists[p].sort(key=lambda x: x[1])
    for c in range(len(clists[p])):
        cid = "{0:06d}".format(plist[p]) + "{0:06d}".format(c+1)
        ids[clists[p][c][0]] = cid

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

Solution (Python):
N, M = map(int,input().split())
PY = [list(map(int,input().split()))+[0] for _ in range(M)]
sort_PY = sorted(PY, key = lambda x:x[1])
city = {}
for i in range(M):
  p, y = sort_PY[i][0], sort_PY[i][1]
  if(p in city):
    city[p] += 1
  else:
    city[p] = 1
  sort_PY[i][2] = city[p]
for p, y, z in PY:
  print(str(p).zfill(6)+str(z).zfill(6))

Solution (Python):









N, M = map(int, input().split(' '))
city = []
for i in range(M):
	
	city.append([i+1]+list(map(int, input().split(' '))))


from operator import itemgetter
city = sorted(city, key=itemgetter(1,2))



x = 1
for n in range(M):
	if n==0:
		city[n].append(1)
	else:
		if city[n][1] != city[n-1][1]:
			x = 1
		else:
			x += 1
		city[n].append(x)			


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


for c in city:
	print(str(c[1]).zfill(6) + str(c[3]).zfill(6))

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


inside_num=1
for i in range(M):
    while L[i][0]!=city_num:
        city_num+=1
        inside_num=1
    L[i][1]=inside_num
    inside_num+=1

L.sort(key=lambda x:x[2])
for l in L:
    print("{:0=6}{:0=6}".format(l[0],l[1]))

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

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

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

city_ids = ["" for i in range(M)]

for P in range(N):
    for x in range(len(cities[P])):
        P_str = str(P + 1)
        x_str = str(x + 1)
        if len(P_str) < 6:
            P_str = "0" * (6 - len(P_str)) + P_str
        if len(x_str) < 6:
            x_str = "0" * (6 - len(x_str)) + x_str
        city_ids[cities[P][x][1]] = P_str + x_str

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

Solution (Python):
N, M = tuple(map(int,input().split()))
A =[]
for i in range(M):
    A.append(tuple(map(int,input().split())))
prev = [0,0]
dic ={}
for city,year in sorted(A):
    if city != prev[0]:
        prev[1] = 1
    dic[(city,year)] = prev[1]
    prev = [city,prev[1]+1]
for i in A:
    print(str.zfill(str(i[0]),6)+str.zfill(str(dic[i]),6))

Solution (Python):
n,m=map(int,input().split())
pys=[]
def make_number(p,x):
    return str(p*10**6+x).zfill(12)
for i in range(m):
    a,b=map(int,input().split())
    pys.append([a,b,i])
pys.sort()
ans=[i for i in range(m)]
c=-1
j=0
for [p,y,s] in pys:
    if c!=p:
        j=1
        c=p
    ans[s]=make_number(p,j)
    j+=1
for i in range(m):
    print(ans[i])

Solution (Python):
N, M = [int(x) for x in input().split()]
PY = [[x] + [int(y) for y in input().split()] + [""] for x in range(M)]
PY.sort(key=lambda x: x[2])

rd = [0]*(N+1)
for i, (x, p, y, s) in enumerate(PY):
    rd[p] += 1
    PY[i][3] = str(p).rjust(6, "0") + str(rd[p]).rjust(6, "0")

PY.sort(key=lambda x: x[0])
for py in PY:
    print(py[3])

Solution (Python):

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

cities = [[i, city[0], city[1]] for i, city in enumerate(cities)]
city_count = [0]*(N+1)
cities.sort(key=lambda x: x[2])
ids = []
for city in cities:
    city_count[city[1]] += 1
    ids.append([city[0], '{:0>6}{:0>6}'.format(city[1], city_count[city[1]])])
ids.sort(key=lambda x: x[0])
for city in ids:
    print(city[1])

Solution (Python):
from bisect import bisect_right
N,M=map(int,input().split())
PY=[]
record=[[] for i in range(N+1)]
for i in range(M):
    P,Y=map(int,input().split())
    PY.append([P,Y])
    record[P].append(Y)
for i in range(1,N+1):
    record[i].sort()
for i in range(M):
    p,y=PY[i][0],PY[i][1]
    order=bisect_right(record[p],y)
    print(str(p).zfill(6)+str(order).zfill(6))

Solution (Python):
(n,m) = map(int, input().split())
pys = []
for i in range(m):
    (a,b) = map(int, input().split())
    pys.append((a,b,i))

pys.sort()
ans = []
cur = -1
j = 0
for (p,y,i) in pys:
    if cur != p:
        j = 1
        cur = p
    
    ans.append((i,"{:0=6}".format(p) + "{:0=6}".format(j)))
    j = j + 1

ans.sort()
for (i, a) in ans:
    print(a)

Solution (Python):
N, M = map(int, input().split())
PY = []
for i in range(M):
    p, y = map(int, input().split())
    PY.append([p, y, i])
PY.sort()
cnt = 1
a = 0
for i in range(M):
    if PY[i][0] == a: cnt += 1
    else: cnt = 1
    a = PY[i][0]
    PY[i][1] = cnt
PY.sort(key=lambda x: x[2])
for i in range(M):
    print(str(PY[i][0]).rjust(6,'0') + str(PY[i][1]).rjust(6,'0'))

Solution (Python):
def ans():
  N, M = map(int,input().split())
  PY = [list(map(int,input().split()))+[0] for _ in range(M)]
  sort_PY = sorted(PY, key = lambda x: x[1])
  city = {}
  for i in range(M):
    p, y, z = sort_PY[i][0], sort_PY[i][1], sort_PY[i][2]
    if(p in city):
      city[p] += 1
    else:
      city[p] = 1
    sort_PY[i][2] = city[p]
  for p, y, z in PY:
    print(str(p).zfill(6) + str(z).zfill(6))
ans()

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

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

def fill(t):
    s = str(t)
    while len(s) < 6:
        s = "0" + s
    return s

Pi.sort(key=lambda x: x[1])
counts = [1] * (N + 1)
for p in Pi:
    city = p[0]
    num = counts[city]
    counts[city] += 1
    p.append(fill(city) + fill(num))

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

Solution (Python):
a,b=map(int,input().split())
l=[]
for _ in range(b):
    c,d=map(int,input().split())
    l.append((c,d))
l2=sorted(sorted(l, key=lambda x:x[1]), key=lambda y:y[0])
m=1
count=0
dic={}
for t in l2:
    if t[0] !=m:
        m=t[0]
        count=1
    else:
        count+=1
    dic[t]=count

for q in l:
    print('{:06d}'.format(q[0])+'{:06d}'.format(dic[q]))

Solution (Python):
N,M = (int(x) for x in input().split())
p_arr = []
for _ in range(M):
    p_arr.append(tuple(int(x) for x in input().split()))

P_dict = {}
for i in range(1, N+1):
    P_dict[i] = []

for i, (p, y) in enumerate(p_arr):
    P_dict[p].append((i+1, y))

P_rank_arr = [0]*(M+1)
for k in P_dict.keys():
    P_dict[k].sort(key=lambda x:x[1])
    for n, (i, _) in enumerate(P_dict[k]):
        P_rank_arr[i] = n+1

for i, (n, _) in enumerate(p_arr):
    print("{:06d}{:06d}".format(n, P_rank_arr[i+1]))

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

for i in range(m):
  p,y=map(int,input().split())
  a[p-1].append((y,i))
  
for i,b in enumerate(a):
  b.sort()
  for j,(y,k) in enumerate(b):
    ans[k]='%06d%06d' % (i+1,j+1)
    
print(*ans,sep='\n')

Solution (Python):
def identify(N: int, M: int, PY: list) -> list:
    _PY = [(i, p, y) for i, (p, y) in enumerate(PY)]
    _PY.sort(key=lambda x: x[2])
    _PY.sort(key=lambda x: x[1])

    now_p = 0
    now_o = 1
    ids = []
    for i, p, _ in _PY:
        if p != now_p:
            now_p = p
            now_o = 1
        ids.append((i, '{p:06}{o:06}'.format(p=p, o=now_o)))
        now_o += 1

    return [i for _, i in sorted(ids, key=lambda x: x[0])]


if __name__ == "__main__":
    N, M = map(int, input().split())
    PY = [tuple(int(s) for s in input().split()) for _ in range(M)]
    for ans in identify(N, M, PY):
        print(ans)

Solution (Python):
import sys
N,M = map(int,input().split())
data = [[i,list(map(int,sys.stdin.readline().rstrip().split()))] for i in range(M)]


sortdata = sorted(data, key=lambda data:data[1])


cnt = 1
sortdata[0].append(1)
for i in range(1,M):
    if sortdata[i][1][0] == sortdata[i-1][1][0]:
        cnt += 1
    else:
        cnt = 1
    sortdata[i].append(cnt)

sortdata = sorted(sortdata, key=lambda data:data[0])
for i in range(M):
    print(str(sortdata[i][1][0]).rjust(6,'0'),end = "")
    print(str(sortdata[i][2]).rjust(6,'0'))

Solution (Python):
N,M = map(int,input().split())
P=[]
for _ in range(M):
  p,y = map(int,input().split())
  P.append((p,y))
d = {}
for p,y in P:
  if p not in d:
    d[p]=[]
  d[p].append(y)
sd = {k:dict(zip(sorted(v),range(1,1+len(v))))
      for k,v in d.items()}
for p,y in P:
  print('%06d%06d' % (p, sd[p][y]))

Solution (Python):
import sys

input = sys.stdin.readline

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

Pm = [0] * M
Ym = [0] * M
ym = [0] * M

Am = [[0 for i in range(2)] for j in range(M)]
Cn = [0] * N

D = {}

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

    Pm[i], Ym[i] = P, Y

    ym[i] = Y

    D[Y] = i

ym.sort()

for i in range(M):
    k = D[ym[i]]

    
    Cn[Pm[k] - 1] += 1
    Am[k] = [Pm[k], Cn[Pm[k] - 1]]

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

Solution (Python):
import sys

input = sys.stdin.readline

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

Pm = [0] * M
Ym = [0] * M
ym = [0] * M

Am = [''] * M
Cn = [0] * N

D = {}

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

    Pm[i], Ym[i] = P, Y

    ym[i] = Y

    D[Y] = i

ym.sort()

for i in range(M):
    k = D[ym[i]]

    
    Cn[Pm[k] - 1] += 1
    Am[k] = str(Pm[k]).rjust(6, '0') + str(Cn[Pm[k] - 1]).rjust(6, '0')

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

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

Pm = [0] * M
Ym = [0] * M
ym = [0] * M

Am = [''] * M
Cn = [0] * N

D = {}

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

    Pm[i], Ym[i] = P, Y

    ym[i] = Y

    D[Y] = i

ym.sort()

for i in range(M):
    k = D[ym[i]]

    
    Cn[Pm[k] - 1] += 1
    Am[k] = str(Pm[k]).rjust(6, '0') + str(Cn[Pm[k] - 1]).rjust(6, '0')

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

Solution (Python):
N, M = map(int,input().split())
C=[0 for _ in range(M)]
count = [0 for _ in range(N)]
for i in range(M):
  p,y = map(int,input().split())
  C[i] = [i, p, y, 0]

C.sort(key = lambda x:x[2])
for i in C:
  count[i[1]-1] +=1
  i[3] = count[i[1]-1]
for i in sorted(C,key = lambda x:x[0]):
  print("{:06d}{:06d}".format(i[1],i[3]))

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

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

city = 0
for i in range(M):
    if data[i][0] != city:
        city = data[i][0]
        num = 1
    data[i][1] = num
    num += 1
    

data.sort(key=lambda x:x[2])
for d in data:
    print("{:0=6}{:0=6}".format(d[0],d[1]))

Solution (Python):
N, M = map(int, input().split())
py_list = [[int(py) for py in input().split()] for i in range(M)]
order_city = [[] for _ in range(N)]
for i, py in enumerate(py_list):
    order_city[py[0]-1].append((i, py[1]))

ans_list = [None]*M

for p, cities in enumerate(order_city):
    for i, city in enumerate(sorted(cities, key=lambda x: x[1])):
        ans_list[city[0]] = "{0:06d}{1:06d}".format(p+1, i+1)

ans = ""
for i in ans_list:
    ans += i+"\n"
 
print(ans[:-1])

Solution (Python):
N, M = map(int, input().split())
py_list = [[int(py) for py in input().split()] for i in range(M)]
order_city = [[] for _ in range(N)]
for i, py in enumerate(py_list):
    order_city[py[0]-1].append((i, py[1]))

ans_list = [None]*M

for p, cities in enumerate(order_city):
    for i, city in enumerate(sorted(cities, key=lambda x: x[1])):
        ans_list[city[0]] = "{0:06d}{1:06d}".format(p+1, i+1)
        
for ans in ans_list:
    print(ans)

Solution (Python):
from collections import defaultdict
from bisect import bisect_left
N, M = map(int, input().split())
A = []
B = defaultdict(list)
 
for i in range(M):
    p, y = map(int, input().split())
    A.append([p, y])
    B[p].append(y)
 
for key in B.keys():
    B[key].sort()




for a in A:
    print("%06d%06d" % (a[0], bisect_left(B[a[0]], a[1])+1))

Solution (Python):
N, M = map(int, input().split())
P, Y = zip(*(map(int, input().split()) for _ in range(M)))
ans = ['' for _ in range(M)]
c = [1 for _ in range(N + 1)]

for i, t in sorted(enumerate(zip(P, Y)), key=lambda x: x[1][1]):
  ans[i] = '{:06}{:06}'.format(t[0], c[t[0]])
  c[t[0]] += 1
  
print('\n'.join(ans))

Solution (Python):
n,m=map(int, input().split())
pre=[0]*n
c=[[j]+[int(i) for i in input().split()] for j in range(m)]
c=sorted(c, key=lambda city: city[2])
newc=[]
for ci in c:
    pre[ci[1]-1]+=1
    newc.append(ci+[pre[ci[1]-1]])
newc=sorted(newc, key=lambda city: city[0])
for city in newc:
    p=str(city[1])
    cnt=str(city[3])
    ans='0'*(6-len(p))+p+'0'*(6-len(cnt))+cnt
    print(ans)

Solution (Python):
N, M = map(int, input().split())
P, Y = zip(*(map(int, input().split()) for _ in range(M)))
ans = ['' for _ in range(M)]
c = [1 for _ in range(N + 1)]
for i, t in sorted(enumerate(zip(P, Y)), key=lambda t: t[1][1]):
    ans[i] = '{:06}{:06}'.format(t[0], c[t[0]])
    c[t[0]] += 1
print('\n'.join(ans))

Solution (Python):
import collections,bisect
N,M=map(int,input().split())
PY=[list(map(int,input().split())) for i in range(M)]
x=collections.defaultdict(list)
for city,year in sorted(PY):
    x[city]+=[year]
for city,year in PY:
    num=bisect.bisect(x[city],year)
    print("%06d%06d"%(city,num))

Solution (Python):
from operator import itemgetter
N,M = map(int,input().split())
S = [list(map(int,input().split()))+[i] for i in range(M)]

S.sort(key=itemgetter(1))
S.sort(key=itemgetter(0))
p = 0
m = 0
j = 1
while m < M:
    if S[m][0] == p:
        S[m][1] = j
        j += 1
        m += 1
    else:
        p += 1
        j = 1
        continue
S.sort(key=itemgetter(2))
for i in range(M):
    print(str(S[i][0]).zfill(6)+str(S[i][1]).zfill(6))

Solution (Python):
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,M=rl()
P=[0]*M
Y=[0]*M
dic = [[] for _ in range(N+1)]
for i in range(M):
    P[i],Y[i] = rl()
    dic[P[i]] += [Y[i]]

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

import bisect
for i in range(M):
    print("{:0>6}{:0>6}".format(P[i], bisect.bisect_left(dic[P[i]],Y[i])+1))

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


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N, M = LI()
P, Y = [], []
for i in range(M):
    j, k = LI()
    P.append(j)
    Y.append(k)








city_records = [[]for i in range(10**6)]
for p, y in zip(P, Y):
    
    
    city_records[p].append(y)



for i in range(len(city_records)):
    if city_records[i] == []:
        continue
    city_records[i].sort()



for p, y in zip(P, Y):
    
    order = bisect.bisect_left(city_records[p], y) + 1
    print(str(p).zfill(6) + str(order).zfill(6))

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


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N, M = LI()
P, Y = [], []
for i in range(M):
    j, k = LI()
    P.append(j)
    Y.append(k)








city_records = [[]for i in range(10**6)]
for p, y in zip(P, Y):
    
    
    city_records[p].append(y)



for i in range(len(city_records)):
    if city_records[i] == []:
        continue
    city_records[i].sort()



for p, y in zip(P, Y):
    
    order = bisect.bisect_left(city_records[p], y) + 1
    print(str(p).zfill(6) + str(order).zfill(6))

Solution (Python):
import collections,bisect
N,M=map(int,input().split())
PY=[list(map(int,input().split())) for i in range(M)]
x=collections.defaultdict(list)
for city,year in sorted(PY):
    x[city]+=[year]
for city,year in PY:
    num=bisect.bisect(x[city],year)
    print("%06d%06d"%(city,num))

Solution (Python):
import collections,bisect
N,M=map(int,input().split())
PY=[list(map(int,input().split())) for i in range(M)]
a=collections.defaultdict(list)
for city,year in sorted(PY):a[city]+=[year]
for city,year in PY:
    z=bisect.bisect(a[city],year)
    print("%06d%06d"%(city,z))